// Jedna instancja wypisuje maksymalny wzrost. #include "message.h" #include "bits/stdc++.h" #include <chrono> #include "teatr.h" struct Timer { Timer() { start = std::chrono::high_resolution_clock::now(); } double elapsed() { return std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1> >> (std::chrono::high_resolution_clock::now() - start).count(); } std::chrono::time_point<std::chrono::high_resolution_clock> start; }; using namespace std; using ll = long long; ll inversions(vector<int>& A) { if (A.size() <= 1) return 0; ll res = 0; int mid = A.size() / 2; vector<int> A1 (A.begin(), A.begin() + mid); vector<int> A2 (A.begin() + mid, A.end()); res += inversions(A1); res += inversions(A2); int ind = 0; for (int i=0; i < A1.size(); i++) { while (ind < A2.size() && A1[i] > A2[ind]) ind ++; res += ind; } merge(A1.begin(), A1.end(), A2.begin(), A2.end(), A.begin()); return res; } int main() { int nodes = NumberOfNodes(); int id = MyNodeId(); int n = GetN(); //Timer t; int slice = (n + nodes - 1) / nodes; int maxi = 0; const int MAX = 1000 * 1000; int begin = slice * id; int end = min(slice * (id + 1), n); vector<int> counts (MAX); for(int i=end; i<n; i++) { counts[GetElement(i)] ++; } vector<int> prefix_counts (MAX+1); for (int i=0; i<MAX; i ++) { prefix_counts[i+1] = prefix_counts[i] + counts[i]; } long long res = 0; vector<int> inside; for(int i=begin; i<end; i++) { int v = GetElement(i); inside.push_back(v); res += prefix_counts[v]; } res += inversions(inside); PutLL(0, res); Send(0); //cerr << int(t.elapsed() * 1000) << " ms" << endl; if (id != 0) return 0; ll res2 = 0; for (int i=0; i < nodes; i ++) { Receive(i); res2 += GetLL(i); } cout << res2 << endl; }
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 | // Jedna instancja wypisuje maksymalny wzrost. #include "message.h" #include "bits/stdc++.h" #include <chrono> #include "teatr.h" struct Timer { Timer() { start = std::chrono::high_resolution_clock::now(); } double elapsed() { return std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1> >> (std::chrono::high_resolution_clock::now() - start).count(); } std::chrono::time_point<std::chrono::high_resolution_clock> start; }; using namespace std; using ll = long long; ll inversions(vector<int>& A) { if (A.size() <= 1) return 0; ll res = 0; int mid = A.size() / 2; vector<int> A1 (A.begin(), A.begin() + mid); vector<int> A2 (A.begin() + mid, A.end()); res += inversions(A1); res += inversions(A2); int ind = 0; for (int i=0; i < A1.size(); i++) { while (ind < A2.size() && A1[i] > A2[ind]) ind ++; res += ind; } merge(A1.begin(), A1.end(), A2.begin(), A2.end(), A.begin()); return res; } int main() { int nodes = NumberOfNodes(); int id = MyNodeId(); int n = GetN(); //Timer t; int slice = (n + nodes - 1) / nodes; int maxi = 0; const int MAX = 1000 * 1000; int begin = slice * id; int end = min(slice * (id + 1), n); vector<int> counts (MAX); for(int i=end; i<n; i++) { counts[GetElement(i)] ++; } vector<int> prefix_counts (MAX+1); for (int i=0; i<MAX; i ++) { prefix_counts[i+1] = prefix_counts[i] + counts[i]; } long long res = 0; vector<int> inside; for(int i=begin; i<end; i++) { int v = GetElement(i); inside.push_back(v); res += prefix_counts[v]; } res += inversions(inside); PutLL(0, res); Send(0); //cerr << int(t.elapsed() * 1000) << " ms" << endl; if (id != 0) return 0; ll res2 = 0; for (int i=0; i < nodes; i ++) { Receive(i); res2 += GetLL(i); } cout << res2 << endl; } |