#include <bits/stdc++.h>
using namespace std;
long long paletta_sort(int N, int V[]);
bool ordinabile(int N, int V[]);
void aggiungi(vector<long long int>& BIT, long long int idx, long long int val);
long long int chiedi(vector<long long int>& BIT, long long int idx);
long long int conta_inversioni(vector<long long int> a, int N);
int main()
{
freopen("input34.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int N;
cin >> N;
int V[N];
for(int i = 0; i < N; i++)
cin >> V[i];
cout << paletta_sort(N, V) << endl;
}
long long paletta_sort(int N, int V[]){
if(!ordinabile(N, V)) return -1;
long long int risultato = 0;
vector<long long int> pari(ceil((float)N / 2));
vector<long long int> dispari(N / 2);
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];
risultato += conta_inversioni(pari, ceil((float)N / 2));
risultato += conta_inversioni(dispari, N / 2);
return risultato;
}
bool ordinabile(int N, int V[]){
bool ordin = true;
for(int i = 0; i < N; i++)
if(V[i] % 2 != i % 2){
ordin = false;
break;
}
return ordin;
}
void aggiungi(vector<long long int>& BIT, long long int index, long long int valore){
index += 1;
while(index < BIT.size()){
BIT[index] += valore;
index += index & -index;
}
}
long long int chiedi(vector<long long int>& BIT, long long int index){
index += 1;
long long int somma = 0;
while(index){
somma += BIT[index];
index -= index & -index;
}
return somma;
}
long long int conta_inversioni(vector<long long int> a, int N){
long long int risultato = 0;
vector<long long int> BIT(N + 1, 0);
vector<long long int> b = a;
sort(b.begin(), b.end());
for(int i = 0; i < N; i++)
a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
for(int i = 0; i < N; i++){
aggiungi(BIT, a[i], 1);
risultato += i - chiedi(BIT, a[i]) + 1;
}
return risultato;
}
Buongiorno, sto provando a risolvere Paletta con un Fenwick tree ma usando l’input 34 dell’esercizio dà questo errore. Chiedo gentilmente un consiglio su come sistemare il problema
Grazie mille