fork download
copy 
  1. #include <cstdio>
  2. #include <cassert>
  3. #include <cstdlib>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. // Declaring variables
  9. static int N;
  10. static int* V;
  11. static long long int numero_ribaltamenti;
  12. long long ans = 0;
  13. int L[1500000], R[1500000];
  14.  
  15.  
  16. void merge(vector<int>& v, int l, int m, int r) {
  17.   int n1 = m-l+1, n2 = r-m, i, j=0, k=l;
  18.   for(i = 0; i < n1; ++i) L[i] = v[l+i];
  19.   for(i = 0; i < n2; ++i) R[i] = v[m+i+1];
  20.  
  21.   i = 0;
  22.   while(i < n1 && j < n2) {
  23.     if(L[i] < R[j]) {
  24.       v[k] = L[i];
  25.       ++i;
  26.     } 
  27.     else {
  28.       v[k] = R[j];
  29.       ++j;
  30.       ans += j + m - k; 
  31.     }
  32.     ++k;
  33.   }
  34.  
  35.   while(i < n1) {
  36.     v[k] = L[i];
  37.     ++i;
  38.     ++k;
  39.   }
  40.  
  41.   while(j < n2) {
  42.     v[k] = R[j];
  43.     ++j;
  44.     ++k;
  45.   }
  46. }
  47.  
  48. void mergesort(vector<int>& v, int l, int r) {
  49.   if(l >= r) return;
  50.  
  51.   int mid = l + (r-l) / 2;
  52.   mergesort(v, l, mid);
  53.   mergesort(v, mid+1, r);
  54.   merge(v, l, mid, r);
  55. }
  56.  
  57. long long paletta_sort(int N, int V[]) {
  58.   vector<int> a, b;
  59.   for (int i = 0; i < N; i++) {
  60.                if (V[i]%2 != i%2) return -1;
  61.   }
  62.   for(int i = 0; i < N; ++i) {
  63.     if(i % 2 == 0)
  64.       a.push_back(V[i]);
  65.     else 
  66.       b.push_back(V[i]);
  67.   }
  68.   mergesort(a, 0, a.size() - 1);
  69.   mergesort(b, 0, b.size() - 1);
  70.  
  71.   return ans;
  72. }
  73.  
  74. int main() {
  75.  
  76.  
  77. 	// Reading input
  78. 	scanf("%d ", &N);
  79. 	V = (int*)malloc(N * sizeof(int));
  80. 	for (int i0 = 0; i0 < N; i0++) {
  81. 		scanf( "%d ", &V[i0]);
  82. 	}
  83.  
  84. 	// Calling functions
  85. 	numero_ribaltamenti = paletta_sort(N, V);
  86.  
  87. 	// Writing output
  88. 	printf( "%lld\n", numero_ribaltamenti);
  89.  
  90.  
  91. 	return 0;
  92. }
  93.  
  94.  
  95.  
  96.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
3
2 1 0
stdout
copy 
1
https://ideone.com/Sq2HZY
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!