#include "dzialka.h" #include "message.h" #include <algorithm> #include <cstdio> #include <vector> using namespace std; typedef long long LL; int main() { int nodes = NumberOfNodes(); int node_id = MyNodeId(); int h = GetFieldHeight(); int w = GetFieldWidth(); // Prepare vector<int> currs; for (int i=node_id; i<w; i+=nodes) { currs.push_back(0); } for (int j=0; j<h; ++j) { for (int i=node_id; i<w; i+=nodes) { auto& curr = currs[(i-node_id) / nodes]; ++curr; if (!IsUsableCell(j, i)) { curr = 0; } PutInt(j%nodes, curr); } } // Shuffle for (int i=0; i<nodes; ++i) { Send(i); } for (int i=0; i<nodes; ++i) { Receive(i); } // Compute LL result = 0; for (int j=node_id; j<h; j+=nodes) { vector<pair<int, int>> stack; // (positiion, distance) for (int i=0; i<w+1; ++i) { int dist = (i<w) ? GetInt(i%nodes) : 0; int pos = i; while (!stack.empty() && stack.back().second >= dist) { int len = (i - stack.back().first); int diff = stack.back().second - dist; if (stack.size() > 1) { diff = min(diff, stack.back().second - stack[stack.size() - 2].second); } LL gain = (LL)diff * len * (len+1) / 2; result += gain; pos = stack.back().first; stack.pop_back(); } stack.push_back(make_pair(pos, dist)); } } // Aggregate if (node_id != 0) { PutLL(0, result); Send(0); } else { for (int i=1; i<nodes; ++i) { Receive(i); result += GetLL(i); } printf("%lld\n", result); } 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 | #include "dzialka.h" #include "message.h" #include <algorithm> #include <cstdio> #include <vector> using namespace std; typedef long long LL; int main() { int nodes = NumberOfNodes(); int node_id = MyNodeId(); int h = GetFieldHeight(); int w = GetFieldWidth(); // Prepare vector<int> currs; for (int i=node_id; i<w; i+=nodes) { currs.push_back(0); } for (int j=0; j<h; ++j) { for (int i=node_id; i<w; i+=nodes) { auto& curr = currs[(i-node_id) / nodes]; ++curr; if (!IsUsableCell(j, i)) { curr = 0; } PutInt(j%nodes, curr); } } // Shuffle for (int i=0; i<nodes; ++i) { Send(i); } for (int i=0; i<nodes; ++i) { Receive(i); } // Compute LL result = 0; for (int j=node_id; j<h; j+=nodes) { vector<pair<int, int>> stack; // (positiion, distance) for (int i=0; i<w+1; ++i) { int dist = (i<w) ? GetInt(i%nodes) : 0; int pos = i; while (!stack.empty() && stack.back().second >= dist) { int len = (i - stack.back().first); int diff = stack.back().second - dist; if (stack.size() > 1) { diff = min(diff, stack.back().second - stack[stack.size() - 2].second); } LL gain = (LL)diff * len * (len+1) / 2; result += gain; pos = stack.back().first; stack.pop_back(); } stack.push_back(make_pair(pos, dist)); } } // Aggregate if (node_id != 0) { PutLL(0, result); Send(0); } else { for (int i=1; i<nodes; ++i) { Receive(i); result += GetLL(i); } printf("%lld\n", result); } return 0; } |