Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- void swap(vector<int>& V, int e, int d){
- int aux = V[e];
- V[e] = V[d];
- V[d] = aux;
- }
- int conta_inv(vector<int>& V, int e, int d){
- if (e>=d) return 0;
- else if (e == d-1){
- if (V[e] > V[d]) {
- swap(V, e, d);
- return 1;
- }
- else return 0;
- }
- else {
- int m = (e+d)/2;
- int inv_e = conta_inv(V, e, m);
- int inv_d = conta_inv(V, m+1, d);
- int cont = 0;
- vector<int> v1,v2;
- for (int x=e; x<=m; x++) v1.push_back(V[x]);
- for (int x=m+1; x<=d; x++) v2.push_back(V[x]);
- int i = 0;
- int j = 0;
- int k = e;
- while (i < v1.size() and j < v2.size()){
- if (v1[i] <= v2[j]){
- V[k] = v1[i];
- i++;
- }
- else {
- V[k] = v2[j];
- j++;
- cont += v1.size() - i;
- }
- k++;
- }
- while (i < v1.size()){
- V[k] = v1[i];
- i++; k++;
- }
- while (j < v2.size()){
- V[k] = v2[j];
- j++; k++;
- }
- return inv_e + inv_d + cont;
- }
- }
- int main(){
- int n;
- while (cin >> n) {
- vector<int> V(n);
- for (int i=0; i<n; i++) cin >> V[i];
- cout << conta_inv(V,0,n-1) << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement