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 // Błędne rozwiązanie do zadania Działka 2. // Na pojedynczym węźle wypisuje liczbę dostępnych kwadracików. #include "dzialka.h" #include "message.h" #include #include using namespace std; #define SIZE(a) ((int)(a).size()) const int N = 755; const int M = 75005; int n, m, id, nodes; int sizeN, sizeM; int d[N], mem[N][N]; int row[M]; int main() { id = MyNodeId(); nodes = NumberOfNodes(); n = GetFieldHeight(); m = GetFieldWidth(); sizeN = (n + nodes - 1)/nodes; sizeM = (m + nodes - 1)/nodes; int l = id*sizeM, r = min(l + sizeM, m); for (int i = 0; i < n; ++i) { for (int j = l; j < r; ++j) { d[j - l] = IsUsableCell(i, j) ? (d[j - l] + 1) : 0; } if ((i + 1) % sizeN == 0 && i + 1 < n) { int here = (i + 1) / sizeN; for (int iter = l; iter < r; ++iter) { mem[here][iter - l] = d[iter - l]; if (here != id) PutInt(here, d[iter - l]); } if (here != id && l < r) { // cout << "SENDING: " << id << ' ' << here << endl; Send(here); } } } l = id*sizeN, r = min(l + sizeN, n); if (l >= n) return 0; if (id > 0) { for (int i = 0; i < nodes; ++i) { int start = i*sizeM; if (start >= m) break; if (i == id) { for (int j = start; j < min(start + sizeM, m); ++j) { row[j] = mem[id][j - start]; } continue; } Receive(i); for (int j = start; j < min(start + sizeM, m); ++j) { row[j] = GetInt(i); } } } vector st; unsigned long long result = 0; for (int i = l; i < r; ++i) { for (int j = 0; j < m; ++j) { row[j] = IsUsableCell(i, j) ? (row[j] + 1) : 0; } st.clear(); st.push_back(-1); for (int j = 0; j < m; ++j) { int last = 0; while (SIZE(st) > 1 && row[st.back()] >= row[j]) { result += 1ULL*(row[st.back()]-max(row[j], (SIZE(st)==2 ? 0 : row[st[SIZE(st)-2]])))*(j - st[SIZE(st)-2])*(j - st[SIZE(st)-2] - 1)/2; st.pop_back(); } st.push_back(j); } while (SIZE(st) > 1) { result += 1LL*(row[st.back()]-(SIZE(st)==2 ? 0 : row[st[SIZE(st)-2]]))*(m - st[SIZE(st)-2])*(m - st[SIZE(st)-2] - 1)/2; st.pop_back(); } } if (id > 0) { PutLL(0, result); Send(0); return 0; } for (int i = 1; i < nodes; ++i) { if (i*sizeN < n) { Receive(i); result += GetLL(i); } } cout << result << '\n'; return 0; }