Paletta: ordinabilità non rispettata su 1 testcase

Aiuto
1

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
Screenshot 2023-05-08 200654934×607 43.1 KB

Cosa c’è di sbagliato in questo codice?

#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;
}
2

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.

3

Grazie mille