#include "dzialka.h" #include "message.h" #include <iostream> #include <queue> const int MAX_SIDE_LENGTH = 75010; const int NUM_OF_CHUNKS = 10; int depth[MAX_SIDE_LENGTH]; int prevDepth[MAX_SIDE_LENGTH]; int main() { const int NumRows = GetFieldHeight(); const int NumCols = GetFieldWidth(); int prevNodeId = MyNodeId() - 1; int nextNodeId = MyNodeId() + 1; int beginRow = MyNodeId() * NumRows / NumberOfNodes(); int endRow = nextNodeId * NumRows / NumberOfNodes() - 1; for (int col = 0; col < NumCols; col++) prevDepth[col] = 0; if (NumberOfNodes() > 1) { int currentRow = endRow; if (nextNodeId < NumberOfNodes() and endRow >= beginRow) { for (int col = 0; col < NumCols; col++) { currentRow = endRow; while (currentRow >= beginRow) { if(IsUsableCell(currentRow, col) == 1) currentRow--; else break; } depth[col] = endRow - currentRow; } } if (MyNodeId() == 0) { for (int chunk = 0; chunk < NUM_OF_CHUNKS; chunk++) { int startOfChunk = chunk * NumCols / NUM_OF_CHUNKS; int endOfChunk = (chunk + 1) * NumCols / NUM_OF_CHUNKS - 1; for (int col = startOfChunk; col <= endOfChunk; col++) PutInt(nextNodeId, depth[col]); Send(nextNodeId); } } else if (nextNodeId == NumberOfNodes()) { for (int chunk = 0; chunk < NUM_OF_CHUNKS; chunk++) { int startOfChunk = chunk * NumCols / NUM_OF_CHUNKS; int endOfChunk = (chunk + 1) * NumCols / NUM_OF_CHUNKS - 1; Receive(prevNodeId); for (int col = startOfChunk; col <= endOfChunk; col++) prevDepth[col] = GetInt(prevNodeId); } } else { for (int chunk = 0; chunk < NUM_OF_CHUNKS; chunk++) { int startOfChunk = chunk * NumCols / NUM_OF_CHUNKS; int endOfChunk = (chunk + 1) * NumCols / NUM_OF_CHUNKS - 1; Receive(prevNodeId); for (int col = startOfChunk; col <= endOfChunk; col++) { prevDepth[col] = GetInt(prevNodeId); if (depth[col] == (endRow - beginRow + 1)) PutInt(nextNodeId, depth[col] + prevDepth[col]); else PutInt(nextNodeId, depth[col]); } Send(nextNodeId); } } } long long count = 0; std::priority_queue<std::pair<int, int>> pq; long long h; long long d; int recentD = 0; int currDepth = 0; for (int row = beginRow; row <= endRow; row++) { pq = std::priority_queue<std::pair<int, int>>(); long long sum = 0; for (int col = 0; col < NumCols; col++) { if (IsUsableCell(row, col)) { depth[col] = prevDepth[col] + 1; } else depth[col] = 0; recentD = col; currDepth = depth[col]; while ((not pq.empty()) and pq.top().first >= currDepth) { d = (long long) recentD - pq.top().second; h = (long long) pq.top().first; sum -= h * d; recentD = pq.top().second; pq.pop(); } if (currDepth != 0) { sum += currDepth * (col + 1 - recentD); pq.push(std::make_pair(currDepth, recentD)); } count += sum; } std::copy(std::begin(depth), std::end(depth), prevDepth); } if (MyNodeId() != 0) { PutLL(0, count); Send(0); } else { for (int i = 1; i < NumberOfNodes(); i++) { Receive(i); count += GetLL(i); } std::cout << count << std::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 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 | #include "dzialka.h" #include "message.h" #include <iostream> #include <queue> const int MAX_SIDE_LENGTH = 75010; const int NUM_OF_CHUNKS = 10; int depth[MAX_SIDE_LENGTH]; int prevDepth[MAX_SIDE_LENGTH]; int main() { const int NumRows = GetFieldHeight(); const int NumCols = GetFieldWidth(); int prevNodeId = MyNodeId() - 1; int nextNodeId = MyNodeId() + 1; int beginRow = MyNodeId() * NumRows / NumberOfNodes(); int endRow = nextNodeId * NumRows / NumberOfNodes() - 1; for (int col = 0; col < NumCols; col++) prevDepth[col] = 0; if (NumberOfNodes() > 1) { int currentRow = endRow; if (nextNodeId < NumberOfNodes() and endRow >= beginRow) { for (int col = 0; col < NumCols; col++) { currentRow = endRow; while (currentRow >= beginRow) { if(IsUsableCell(currentRow, col) == 1) currentRow--; else break; } depth[col] = endRow - currentRow; } } if (MyNodeId() == 0) { for (int chunk = 0; chunk < NUM_OF_CHUNKS; chunk++) { int startOfChunk = chunk * NumCols / NUM_OF_CHUNKS; int endOfChunk = (chunk + 1) * NumCols / NUM_OF_CHUNKS - 1; for (int col = startOfChunk; col <= endOfChunk; col++) PutInt(nextNodeId, depth[col]); Send(nextNodeId); } } else if (nextNodeId == NumberOfNodes()) { for (int chunk = 0; chunk < NUM_OF_CHUNKS; chunk++) { int startOfChunk = chunk * NumCols / NUM_OF_CHUNKS; int endOfChunk = (chunk + 1) * NumCols / NUM_OF_CHUNKS - 1; Receive(prevNodeId); for (int col = startOfChunk; col <= endOfChunk; col++) prevDepth[col] = GetInt(prevNodeId); } } else { for (int chunk = 0; chunk < NUM_OF_CHUNKS; chunk++) { int startOfChunk = chunk * NumCols / NUM_OF_CHUNKS; int endOfChunk = (chunk + 1) * NumCols / NUM_OF_CHUNKS - 1; Receive(prevNodeId); for (int col = startOfChunk; col <= endOfChunk; col++) { prevDepth[col] = GetInt(prevNodeId); if (depth[col] == (endRow - beginRow + 1)) PutInt(nextNodeId, depth[col] + prevDepth[col]); else PutInt(nextNodeId, depth[col]); } Send(nextNodeId); } } } long long count = 0; std::priority_queue<std::pair<int, int>> pq; long long h; long long d; int recentD = 0; int currDepth = 0; for (int row = beginRow; row <= endRow; row++) { pq = std::priority_queue<std::pair<int, int>>(); long long sum = 0; for (int col = 0; col < NumCols; col++) { if (IsUsableCell(row, col)) { depth[col] = prevDepth[col] + 1; } else depth[col] = 0; recentD = col; currDepth = depth[col]; while ((not pq.empty()) and pq.top().first >= currDepth) { d = (long long) recentD - pq.top().second; h = (long long) pq.top().first; sum -= h * d; recentD = pq.top().second; pq.pop(); } if (currDepth != 0) { sum += currDepth * (col + 1 - recentD); pq.push(std::make_pair(currDepth, recentD)); } count += sum; } std::copy(std::begin(depth), std::end(depth), prevDepth); } if (MyNodeId() != 0) { PutLL(0, count); Send(0); } else { for (int i = 1; i < NumberOfNodes(); i++) { Receive(i); count += GetLL(i); } std::cout << count << std::endl; return 0; } } |