#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include "message.h" #include "teatr.h" using namespace std; int tab[5]={5,2,4,4,3}; int num=5; int main(){ if(MyNodeId()==0){ long long int wynik=0; int n = GetN(); if(n <= 1500){ for(int i=0; i < n; ++i){ int p = GetElement(i); for(int j=i+1; j < n; ++j){ int q = GetElement(j); if(p > q){ wynik++; } } } }else{ int m = 5; if(n > 500000){ m = 5; }else{ while(m < n && m*n < 2500000 && m < 1000){ m++; } } int zlicz[m+1]; for(int i=0; i <= m; ++i){ zlicz[i]=0; } for(int i=0; i < n; ++i){ int p = GetElement(i); for(int j=p+1; j <= m; ++j){ if(zlicz[j]>0){ wynik+=zlicz[j]; } } if(p >= m){ zlicz[m]++; }else{ zlicz[p]++; } } } cout << wynik; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include "message.h" #include "teatr.h" using namespace std; int tab[5]={5,2,4,4,3}; int num=5; int main(){ if(MyNodeId()==0){ long long int wynik=0; int n = GetN(); if(n <= 1500){ for(int i=0; i < n; ++i){ int p = GetElement(i); for(int j=i+1; j < n; ++j){ int q = GetElement(j); if(p > q){ wynik++; } } } }else{ int m = 5; if(n > 500000){ m = 5; }else{ while(m < n && m*n < 2500000 && m < 1000){ m++; } } int zlicz[m+1]; for(int i=0; i <= m; ++i){ zlicz[i]=0; } for(int i=0; i < n; ++i){ int p = GetElement(i); for(int j=p+1; j <= m; ++j){ if(zlicz[j]>0){ wynik+=zlicz[j]; } } if(p >= m){ zlicz[m]++; }else{ zlicz[p]++; } } } cout << wynik; } return 0; } |