Buongiorno a tutti!
Sto provando a risolvere paletta sort implementando un segment tree, ma sottoponendolo ottengo 52 punti su 100: falliscono i casi 18, 33 e 35, i quali dicono “risposta errata: numero di scambi errato” (il mio programma ha capito che l’array può essere ordinato, ma ha dato il numero sbaglio di scambi necessari) e non riesco proprio a capire il perchè.
Qualcuno saprebbe aiutarmi?
long long int tree0[750000*6], tree1[750000*6]; // tree0 contiene l'albero per i numeri pari, tree1 per i numeri dispari
void update(long long int* tree, int left, int right, int index, int number) { // Aggiunge un numero all'albero
// tree - albero da aggiornare
// left - inizio del range coperto dal nodo corrente
// right - fine del range coperto dal nodo corrente
// index - posizione del nodo corrente nell'array
// number - numero da inserire
if (left==right) tree[index]=1; // Il nodo corrente è una foglia dell'albero
else {
int mid = (left+right) >> 1;
if (number > mid) // Il numero si trova nel figlio di destra
update(tree, mid+1, right, 2*index+1, number);
else // Il numero si trova nel figlio di sinistra
update(tree, left, mid, 2*index, number);
tree[index] = tree[2*index] + tree[2*index+1]; // Aggiorna il nodo corrente
}
}
long long int query(long long int* tree, int left, int right, int index, int l, int r) { // Restituisce il numero di elementi nel range (l, r)
// tree - albero da leggere
// left - inizio del range coperto dal nodo corrente
// right - fine del range coperto dal nodo corrente
// index - posizione del nodo corrente nell'array
// l - inizio del range nella query
// r - fine del range nella query
if (l>r) return 0;
if (l==left && r==right) return tree[index]; // Il risultato della query è contenuto in questo nodo
int mid = (left+right) >> 1;
return query(tree, left, mid, 2*index, l, (r<mid)? r:mid)
+query(tree, mid+1, right, 2*index+1, (l>mid+1)? l:(mid+1), r); // Restituisce il risultato della query combinando i nodi figli
}
long long int paletta_sort(int N, int* V) {
long long int res = 0;
int mx = (N-(N%2)-2)/2;
for (int i=0; i<N; i++) {
if (i%2 != V[i]%2)
return -1;
if (i%2) {
res += query(tree1, 0, mx, 1, V[i]/2, mx);
update(tree1, 0, mx, 1, V[i]/2);
} else {
res += query(tree0, 0, mx, 1, V[i]/2, mx);
update(tree0, 0, mx, 1, V[i]/2);
}
}
return res;
}