#include <iostream> #include <vector> #include "teatr.h" #include "message.h" #define DEBUG if (0) #define COUT cout << "\e[36m" #define VAR(v) " [\e[32m" << #v << "\e[36m=\e[91m" << v << "\e[36m] " #define ENDL "\e[39m" << endl using namespace std; long long int n,inwersje; vector<int> orgvec; void merge_sort (int b, int e) { if(b>=e) return; int mid = (e+b)/2; merge_sort(b, mid); merge_sort(mid+1, e); vector<int> rvec, lvec; for(int i = b; i <= e; ++i) { if(i <= mid) lvec.push_back(orgvec[i]); else rvec.push_back(orgvec[i]); } unsigned int lp = 0, rp = 0; for(int i = b; i <= e; i++) { if(lp < lvec.size() && rp < rvec.size()) { if(lvec[lp] >= rvec[rp]) { orgvec[i] = lvec[lp]; lp++; inwersje += rp; } else { orgvec[i] = rvec[rp]; rp++; } } else { if(lp < lvec.size()) { orgvec[i] = lvec[lp]; lp++; inwersje += rp; } else if(rp < rvec.size()) { orgvec[i] = rvec[rp]; rp++; } } } } int main() { //ios_base::sync_with_stdio(0); int z =1; //cin >> z; if(MyNodeId() == 0)//for(int zi = 0; zi < z; ++zi) { n = GetN(); orgvec.resize(n); for(int ni = 0; ni < n; ++ni) { orgvec[ni] = GetElement(n-ni-1); } inwersje = 0; merge_sort(0, n-1); //for(auto el : orgvec) // cout << el << " "; cout << endl << inwersje << endl; } 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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <iostream> #include <vector> #include "teatr.h" #include "message.h" #define DEBUG if (0) #define COUT cout << "\e[36m" #define VAR(v) " [\e[32m" << #v << "\e[36m=\e[91m" << v << "\e[36m] " #define ENDL "\e[39m" << endl using namespace std; long long int n,inwersje; vector<int> orgvec; void merge_sort (int b, int e) { if(b>=e) return; int mid = (e+b)/2; merge_sort(b, mid); merge_sort(mid+1, e); vector<int> rvec, lvec; for(int i = b; i <= e; ++i) { if(i <= mid) lvec.push_back(orgvec[i]); else rvec.push_back(orgvec[i]); } unsigned int lp = 0, rp = 0; for(int i = b; i <= e; i++) { if(lp < lvec.size() && rp < rvec.size()) { if(lvec[lp] >= rvec[rp]) { orgvec[i] = lvec[lp]; lp++; inwersje += rp; } else { orgvec[i] = rvec[rp]; rp++; } } else { if(lp < lvec.size()) { orgvec[i] = lvec[lp]; lp++; inwersje += rp; } else if(rp < rvec.size()) { orgvec[i] = rvec[rp]; rp++; } } } } int main() { //ios_base::sync_with_stdio(0); int z =1; //cin >> z; if(MyNodeId() == 0)//for(int zi = 0; zi < z; ++zi) { n = GetN(); orgvec.resize(n); for(int ni = 0; ni < n; ++ni) { orgvec[ni] = GetElement(n-ni-1); } inwersje = 0; merge_sort(0, n-1); //for(auto el : orgvec) // cout << el << " "; cout << endl << inwersje << endl; } return 0; } |