Ciao a tutti, stavo risolvendo paletta con il Fenwick Tree e avevo scritto questo codice:
#include <cstdio>
#include <cstdlib>
//INIZIO paletta.cpp
#include <vector>
using namespace std;
vector<int> Fenwick;
void aggiorna(int ind){
while(ind<Fenwick.size()){
Fenwick[ind]++;
ind=ind|(ind+1);
}
}
int chiedi(int ind){
int ret;
while(ind>-1){
ret+=Fenwick[ind];
ind=(ind&(ind+1))-1;
}
return ret;
}
long long numOperazioni(vector<int> V, int size){
long long ret=0;
Fenwick=vector<int>(size, 0);
for(int i=0; i<size; i++){
V[i]/=2;
ret+=i-chiedi(V[i]);
aggiorna(V[i]);
}
return ret;
}
long long paletta_sort(int N, int V[]){
for(int i=0; i<N; i++){
if(i%2!=V[i]%2){
return -1;
}
}
int sizePari=N/2, sizeDispari=N/2;
if(N%2!=0){
sizePari++;
}
vector<int> pari(sizePari), dispari(sizeDispari);
for(int i=0; i<N; i+=2){
pari[i/2]=V[i];
}
for(int i=1; i<N; i+=2){
dispari[i/2]=V[i];
}
return numOperazioni(pari, sizePari)+numOperazioni(dispari, sizeDispari);
}
//FINE paletta.cpp
static int N;
static int* V;
static long long int numero_ribaltamenti;
static FILE *fr, *fw;
int main(){
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
fscanf(fr, "%d ", &N);
V = (int*)malloc(N * sizeof(int));
for (int i0 = 0; i0 < N; i0++) {
fscanf(fr, "%d ", &V[i0]);
}
// Calling functions
numero_ribaltamenti = paletta_sort(N, V);
// Writing output
fprintf(fw, "%lld\n", numero_ribaltamenti);
fclose(fr);
fclose(fw);
return 0;
return 0;
}
Solo che quando lo invio fa 20/100 perché dà tutte le subtask come parzialmente corrette (distingue le sequenze ordinabili da quelle non ordinabili ma non da il corretto numero di scambi necessari per ordinare). Uno dei casi di test che mi dà come errati è il secondo esempio, che quando eseguo in locale invece dà la risposta giusta.
Ho provato anche un compilatore online (OnlineGDB) e mi da un’altra risposta ancora (un numero negativo (che non darebbe quindi output parzialmente corretto) intorno al -196590 che cambia da volta a volta). Immagino ci sia qualcosa nel mio codice che ogni compilatore decide di interpretare a suo piacere, ma non saprei cosa, qualcuno saprebbe aiutarmi?
Grazie