# Paletta: ordinabilità non rispettata su 1 testcase

**URL:** <https://forum.olinfo.it/t/paletta-ordinabilita-non-rispettata-su-1-testcase/8240>\
**Category:** Aiuto\
**Created:** [8 Maggio 2023, 6:11pm UTC](https://forum.olinfo.it/t/paletta-ordinabilita-non-rispettata-su-1-testcase/8240 "2023-05-08T18:11:58Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![VantoDiVallauri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7ba0ec/32.png) [@VantoDiVallauri](https://forum.olinfo.it/u/VantoDiVallauri)\
**Post date:** [8 Maggio 2023, 6:11pm UTC](https://forum.olinfo.it/t/paletta-ordinabilita-non-rispettata-su-1-testcase/8240/1 "2023-05-08T18:11:59Z")

</div>

Ciao a tutti, ho risolto paletta usando il mergesort per contare quante volte avvengono gli scambi. Solo che mi dà un testcase sbagliato per ordinabilità non rispettata mentre tutte le altre sono giuste

 ![Screenshot 2023-05-08 200654](https://forum.olinfo.it/uploads/default/original/2X/9/9ca031f1ebe2378b1c86f640ebbbf4e622f50dc7.png)  
Cosa c’è di sbagliato in questo codice?

```auto
#include <bits/stdc++.h>
using namespace std;

long long ans = 0;
int L[375001], R[375001];

void merge(vector<int>& v, int l, int m, int r) {
  int n1 = m-l+1, n2 = r-m, i, j=0, k=l;
  for(i = 0; i < n1; ++i) L[i] = v[l+i];
  for(i = 0; i < n2; ++i) R[i] = v[m+i+1];

  i = 0;
  while(i < n1 && j < n2) {
    if(L[i] < R[j]) {
      v[k] = L[i];
      ++i;
    } else {
      v[k] = R[j];
      ++j;
      ans += j + m - k; // aumento numero di scambi
    }
    ++k;
  }

  while(i < n1) {
    v[k] = L[i];
    ++i;
    ++k;
  }

  while(j < n2) {
    v[k] = R[j];
    ++j;
    ++k;
  }
}

void mergesort(vector<int>& v, int l, int r) {
  if(l >= r) return;

  int mid = l + (r-l) / 2;
  mergesort(v, l, mid);
  mergesort(v, mid+1, r);
  merge(v, l, mid, r);
}

long long paletta_sort(int N, int V[]) {
  vector<int> a, b;
  for(int i = 0; i < N; ++i) {
    if(i % 2 == 0)
      a.push_back(V[i]);
    else 
      b.push_back(V[i]);
  }
  mergesort(a, 0, a.size() - 1);
  mergesort(b, 0, b.size() - 1);

  for(int i = 0; i < b.size(); ++i) {
    if(b[i] < a[i]) return -1;
  }
  return ans;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [8 Maggio 2023, 8:28pm UTC](https://forum.olinfo.it/t/paletta-ordinabilita-non-rispettata-su-1-testcase/8240/2 "2023-05-08T20:28:01Z")

</div>

Ciao, è la tua condizione di non ordinabilità che non va:  
for(int i = 0; i \< b.size(); ++i)  
if(b[i] \< a[i]) return -1;

La tua condizione fallisce, ad esempio, con questo input:  
8  
6 4 1 5 0 3 2 7

Per l’ordinabilità devi semplicemente verificare che tutti i pari siano in posizione pari e i dispari in posizione dispari.

---

<div class="post-metadata">

**Author:** ![VantoDiVallauri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7ba0ec/32.png) [@VantoDiVallauri](https://forum.olinfo.it/u/VantoDiVallauri)\
**Post date:** [9 Maggio 2023, 1:59pm UTC](https://forum.olinfo.it/t/paletta-ordinabilita-non-rispettata-su-1-testcase/8240/3 "2023-05-09T13:59:31Z")

</div>

Grazie mille