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