#include <iostream> #include "teatr.h" #include "message.h" #include <vector> using namespace std; //Wezmy to rozwalmy przy pomocy merge sort vector<int> rozloz(long long &wynik, vector<int> tab); vector<int> skladaj(long long &wynik, vector<int> tab1, vector<int> tab2); /* int NumberOfNodes(){ return 1; } int GetN(){ int x; cin >> x; return x; } int MyNodeId(){ return 1; } int GetElement(int i){ cin >> i; return i; } void wypisz(vector<int> tab) { int n=tab.size(); for(int i=0; i<n; i++) { cout << tab[i] << " "; } cout << endl; }*/ /* */ void wysylaj(vector<int> tab) { int n=tab.size(); for(int i=0; i<n; i++) { PutInt(0, tab[i]); Send(0); } }/* */ int main() { int n = GetN(); int id = MyNodeId(); long long wynik = 0; vector<int> tab; if(n<NumberOfNodes()){ for(int i=0; i<n ; i++) { tab.push_back(GetElement(i)); } }else if(id<n){ tab.push_back(GetElement(id)); } //wypisz(tab); tab = rozloz(wynik, tab); //wypisz(tab); if(id!=0) { //PutInt(0,wynik); //PutInt(0,tab.size()); //wysylaj(tab); }else{ cout << wynik << endl; } return 0; } vector<int> rozloz(long long &wynik, vector<int> tab){ //wypisz(tab); vector<int> t1, t2; int n=tab.size(); for(int i=0; i<n/2; i++){ t1.push_back(tab[i]); } for(int i=n/2; i<n; i++){ t2.push_back(tab[i]); } if(n>=4){ //wypisz(t1); t1 = rozloz(wynik, t1); //wypisz(t1); t2 = rozloz(wynik, t2); return skladaj(wynik, t1, t2); }else if(n==3){ t2 = rozloz(wynik, t2); return skladaj(wynik, t1, t2); }else{ return skladaj(wynik, t1, t2); } } vector<int> skladaj(long long &wynik, vector<int> tab1, vector<int> tab2) //tab1 jest bardziej blizzsze widowni { vector<int> t; int n = tab1.size(), m = tab2.size(); int point1=0, point2=0; for(int i=0; i<n+m; i++){ //wypisz(t); if(point1 == tab1.size()){ t.push_back(tab2[point2++]); }else if(point2 == tab2.size()){ t.push_back(tab1[point1++]); }else{ if(tab1[point1]<=tab2[point2]){ t.push_back(tab1[point1++]); }else{ wynik+=n-point2; t.push_back(tab2[point2++]); } } } return t; }
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | #include <iostream> #include "teatr.h" #include "message.h" #include <vector> using namespace std; //Wezmy to rozwalmy przy pomocy merge sort vector<int> rozloz(long long &wynik, vector<int> tab); vector<int> skladaj(long long &wynik, vector<int> tab1, vector<int> tab2); /* int NumberOfNodes(){ return 1; } int GetN(){ int x; cin >> x; return x; } int MyNodeId(){ return 1; } int GetElement(int i){ cin >> i; return i; } void wypisz(vector<int> tab) { int n=tab.size(); for(int i=0; i<n; i++) { cout << tab[i] << " "; } cout << endl; }*/ /* */ void wysylaj(vector<int> tab) { int n=tab.size(); for(int i=0; i<n; i++) { PutInt(0, tab[i]); Send(0); } }/* */ int main() { int n = GetN(); int id = MyNodeId(); long long wynik = 0; vector<int> tab; if(n<NumberOfNodes()){ for(int i=0; i<n ; i++) { tab.push_back(GetElement(i)); } }else if(id<n){ tab.push_back(GetElement(id)); } //wypisz(tab); tab = rozloz(wynik, tab); //wypisz(tab); if(id!=0) { //PutInt(0,wynik); //PutInt(0,tab.size()); //wysylaj(tab); }else{ cout << wynik << endl; } return 0; } vector<int> rozloz(long long &wynik, vector<int> tab){ //wypisz(tab); vector<int> t1, t2; int n=tab.size(); for(int i=0; i<n/2; i++){ t1.push_back(tab[i]); } for(int i=n/2; i<n; i++){ t2.push_back(tab[i]); } if(n>=4){ //wypisz(t1); t1 = rozloz(wynik, t1); //wypisz(t1); t2 = rozloz(wynik, t2); return skladaj(wynik, t1, t2); }else if(n==3){ t2 = rozloz(wynik, t2); return skladaj(wynik, t1, t2); }else{ return skladaj(wynik, t1, t2); } } vector<int> skladaj(long long &wynik, vector<int> tab1, vector<int> tab2) //tab1 jest bardziej blizzsze widowni { vector<int> t; int n = tab1.size(), m = tab2.size(); int point1=0, point2=0; for(int i=0; i<n+m; i++){ //wypisz(t); if(point1 == tab1.size()){ t.push_back(tab2[point2++]); }else if(point2 == tab2.size()){ t.push_back(tab1[point1++]); }else{ if(tab1[point1]<=tab2[point2]){ t.push_back(tab1[point1++]); }else{ wynik+=n-point2; t.push_back(tab2[point2++]); } } } return t; } |