#include "dzialka.h" #include "message.h" #include <iostream> #include <vector> #include <iterator> using namespace std; struct Node { Node(int h = 0, long long s1 = 0, long long s2 = 0) : height(h), sumOfRectangles(s1), sumOfNums(s2) {} int height; long long sumOfRectangles; long long sumOfNums; }; bool operator<(const Node &n1, const Node &n2) { return n1.height < n2.height; } int main() { int myNodeId = MyNodeId(); int numOfNodes = NumberOfNodes(); int numOfRows = GetFieldHeight(); int numOfCols = GetFieldWidth(); vector<int> heights; heights.resize(numOfCols / numOfNodes + 1, 0); int step = numOfRows / numOfNodes; int whoToSend = 0, curr = step; if (step != 0) { for (int row = 0; row < numOfRows; ++row, ++curr) { if (curr == step) { PutChar(whoToSend, 'a'); for (int i = 0, col = myNodeId; col < numOfCols; ++i, col += numOfNodes) { PutInt(whoToSend, heights[i]); } Send(whoToSend); curr = 0; ++whoToSend; if (whoToSend == numOfNodes) { break; } } for (int col = myNodeId, i = 0; col < numOfCols; col += numOfNodes, ++i) { if (IsUsableCell(row, col)) { ++heights[i]; } else { heights[i] = 0; } } } } int startRow = numOfRows / numOfNodes * myNodeId; int endRow = startRow + numOfRows / numOfNodes; if (myNodeId == numOfNodes - 1) { endRow = numOfRows; } if (endRow == 0) { return 0; } vector<int> hs; hs.resize(numOfCols, 0); if (step != 0) { for (int i = 0; i < numOfNodes; ++i) { Receive(i); GetChar(i); for (int j = i; j < numOfCols; j += numOfNodes) { hs[j] = GetInt(i); } } } long long rectangles = 0; vector<Node> rects; rects.resize(numOfRows); for (int row = startRow; row < endRow; ++row) { int rectsMaxPos = 0; for (int currCol = numOfCols - 1; currCol >= 0; --currCol) { if (not IsUsableCell(row, currCol)) { hs[currCol] = 0; rectsMaxPos = 0; continue; } if (rectsMaxPos == 0) { rects[0].height = ++hs[currCol]; rects[0].sumOfRectangles = rects[0].height; rects[0].sumOfNums = 1; rectsMaxPos = 1; rectangles += rects[0].sumOfRectangles; continue; } Node newNode; newNode.height = ++hs[currCol]; int pos = distance(rects.begin(), lower_bound(rects.begin(), rects.begin() + rectsMaxPos, newNode)); rects[pos].height = hs[currCol]; if (pos == 0) { rects[0].sumOfNums = rects[rectsMaxPos - 1].sumOfNums + 1; rects[0].sumOfRectangles = rects[0].height * rects[0].sumOfNums; rectsMaxPos = 1; rectangles += rects[0].sumOfRectangles; continue; } rects[pos].sumOfNums = rects[rectsMaxPos - 1].sumOfNums + 1; rects[pos].sumOfRectangles = rects[pos].height * (rects[pos].sumOfNums - rects[pos - 1].sumOfNums) + rects[pos - 1].sumOfRectangles; rectsMaxPos = pos + 1; rectangles += rects[pos].sumOfRectangles; } } if (step == 0) { cout << rectangles << endl; return 0; } PutLL(numOfNodes - 1, rectangles); Send(numOfNodes - 1); if (myNodeId != numOfNodes - 1) { return 0; } long long finalRes = 0; for (int i = 0; i < numOfNodes; ++i) { int sender = Receive(-1); finalRes += GetLL(sender); } cout << finalRes << 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 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 125 126 127 | #include "dzialka.h" #include "message.h" #include <iostream> #include <vector> #include <iterator> using namespace std; struct Node { Node(int h = 0, long long s1 = 0, long long s2 = 0) : height(h), sumOfRectangles(s1), sumOfNums(s2) {} int height; long long sumOfRectangles; long long sumOfNums; }; bool operator<(const Node &n1, const Node &n2) { return n1.height < n2.height; } int main() { int myNodeId = MyNodeId(); int numOfNodes = NumberOfNodes(); int numOfRows = GetFieldHeight(); int numOfCols = GetFieldWidth(); vector<int> heights; heights.resize(numOfCols / numOfNodes + 1, 0); int step = numOfRows / numOfNodes; int whoToSend = 0, curr = step; if (step != 0) { for (int row = 0; row < numOfRows; ++row, ++curr) { if (curr == step) { PutChar(whoToSend, 'a'); for (int i = 0, col = myNodeId; col < numOfCols; ++i, col += numOfNodes) { PutInt(whoToSend, heights[i]); } Send(whoToSend); curr = 0; ++whoToSend; if (whoToSend == numOfNodes) { break; } } for (int col = myNodeId, i = 0; col < numOfCols; col += numOfNodes, ++i) { if (IsUsableCell(row, col)) { ++heights[i]; } else { heights[i] = 0; } } } } int startRow = numOfRows / numOfNodes * myNodeId; int endRow = startRow + numOfRows / numOfNodes; if (myNodeId == numOfNodes - 1) { endRow = numOfRows; } if (endRow == 0) { return 0; } vector<int> hs; hs.resize(numOfCols, 0); if (step != 0) { for (int i = 0; i < numOfNodes; ++i) { Receive(i); GetChar(i); for (int j = i; j < numOfCols; j += numOfNodes) { hs[j] = GetInt(i); } } } long long rectangles = 0; vector<Node> rects; rects.resize(numOfRows); for (int row = startRow; row < endRow; ++row) { int rectsMaxPos = 0; for (int currCol = numOfCols - 1; currCol >= 0; --currCol) { if (not IsUsableCell(row, currCol)) { hs[currCol] = 0; rectsMaxPos = 0; continue; } if (rectsMaxPos == 0) { rects[0].height = ++hs[currCol]; rects[0].sumOfRectangles = rects[0].height; rects[0].sumOfNums = 1; rectsMaxPos = 1; rectangles += rects[0].sumOfRectangles; continue; } Node newNode; newNode.height = ++hs[currCol]; int pos = distance(rects.begin(), lower_bound(rects.begin(), rects.begin() + rectsMaxPos, newNode)); rects[pos].height = hs[currCol]; if (pos == 0) { rects[0].sumOfNums = rects[rectsMaxPos - 1].sumOfNums + 1; rects[0].sumOfRectangles = rects[0].height * rects[0].sumOfNums; rectsMaxPos = 1; rectangles += rects[0].sumOfRectangles; continue; } rects[pos].sumOfNums = rects[rectsMaxPos - 1].sumOfNums + 1; rects[pos].sumOfRectangles = rects[pos].height * (rects[pos].sumOfNums - rects[pos - 1].sumOfNums) + rects[pos - 1].sumOfRectangles; rectsMaxPos = pos + 1; rectangles += rects[pos].sumOfRectangles; } } if (step == 0) { cout << rectangles << endl; return 0; } PutLL(numOfNodes - 1, rectangles); Send(numOfNodes - 1); if (myNodeId != numOfNodes - 1) { return 0; } long long finalRes = 0; for (int i = 0; i < numOfNodes; ++i) { int sender = Receive(-1); finalRes += GetLL(sender); } cout << finalRes << endl; } |