#include <iostream> #include <math.h> #include "dzialka.h" #include "message.h" #define LL long long #define MAX_SIZE 75010 #define MIN_ROWS 10000 using namespace std; int main() { int numberOfNodes, nodeId, height, width, value, last, block, b_top, b_bottom; int bottom[MAX_SIZE], top[MAX_SIZE]; LL result = 0, tmp_result = 0, cache[MAX_SIZE]; int rows, first_row, last_row, max_rows; bool bc[MAX_SIZE]; numberOfNodes = NumberOfNodes(); nodeId = MyNodeId(); height = GetFieldHeight(); width = GetFieldWidth(); rows = max(height / numberOfNodes + 1, MIN_ROWS); first_row = nodeId * rows; if (first_row >= height) return 0; last_row = min(first_row + rows, height); for (int i = 0; i < width; i++){ bottom[i] = 0; top[i] = 0; cache[i] = 0; bc[i] = true; } for (int i = first_row; i < last_row; i++) { last = 0; for (int j = 0; j < width; j++) { value = IsUsableCell(i, j); if (value == 1) { result++; result += last; if (top[j] > 0) { tmp_result = top[j]; block = top[j] + 1 ; for (int k = 1; k <= last; k++ ) { if (block >= top[j-k]) { tmp_result += 1LL * (k - 1) * (block - 1); tmp_result += cache[j-k]; break; } } result += tmp_result; cache[j] = tmp_result; } else { cache[j] = 0; } last++; top[j]++; if (bc[j]) bottom[j]++; } else { last = 0; top[j] = 0; cache[j] = 0; if (bc[j]) bc[j] = false; } } } if (nodeId > 0) { PutLL(0, result); for (int i = 0; i < width; i++) PutInt(0, bottom[i]); for (int i = 0; i < width; i++) PutInt(0, top[i]); Send(0); return 0; } else { for (int j = 1; j < numberOfNodes; j++) { if (j*rows >= height) break; Receive(j); result += GetLL(j); last = 0; for (int i = 0; i < width; i++){ bottom[i] = GetInt(j); if (top[i] > 0 && bottom[i] > 0) { b_top = top[i]; b_bottom = bottom[i]; tmp_result = b_top * b_bottom; for (int k = 1; k <= last; k++) { if (b_bottom >= bottom[i-k]) { if (b_top >= top[i-k]) { tmp_result += cache[i-k]; break; } else { b_bottom = bottom[i-k]; tmp_result += b_top * b_bottom; } } else { if (b_top >= top[i-k]) { b_top = top[i-k]; tmp_result += b_top * b_bottom; } else { tmp_result += b_top * b_bottom; } } } result += tmp_result; cache[i] = tmp_result; last++; } else { cache[i] = 0; last = 0; } } max_rows = min((j + 1) * rows, height) - j * rows; for (int i = 0; i < width; i++) { value = GetInt(j); if (value == max_rows) top[i] += value; else top[i] = value; } } } cout << result << 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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | #include <iostream> #include <math.h> #include "dzialka.h" #include "message.h" #define LL long long #define MAX_SIZE 75010 #define MIN_ROWS 10000 using namespace std; int main() { int numberOfNodes, nodeId, height, width, value, last, block, b_top, b_bottom; int bottom[MAX_SIZE], top[MAX_SIZE]; LL result = 0, tmp_result = 0, cache[MAX_SIZE]; int rows, first_row, last_row, max_rows; bool bc[MAX_SIZE]; numberOfNodes = NumberOfNodes(); nodeId = MyNodeId(); height = GetFieldHeight(); width = GetFieldWidth(); rows = max(height / numberOfNodes + 1, MIN_ROWS); first_row = nodeId * rows; if (first_row >= height) return 0; last_row = min(first_row + rows, height); for (int i = 0; i < width; i++){ bottom[i] = 0; top[i] = 0; cache[i] = 0; bc[i] = true; } for (int i = first_row; i < last_row; i++) { last = 0; for (int j = 0; j < width; j++) { value = IsUsableCell(i, j); if (value == 1) { result++; result += last; if (top[j] > 0) { tmp_result = top[j]; block = top[j] + 1 ; for (int k = 1; k <= last; k++ ) { if (block >= top[j-k]) { tmp_result += 1LL * (k - 1) * (block - 1); tmp_result += cache[j-k]; break; } } result += tmp_result; cache[j] = tmp_result; } else { cache[j] = 0; } last++; top[j]++; if (bc[j]) bottom[j]++; } else { last = 0; top[j] = 0; cache[j] = 0; if (bc[j]) bc[j] = false; } } } if (nodeId > 0) { PutLL(0, result); for (int i = 0; i < width; i++) PutInt(0, bottom[i]); for (int i = 0; i < width; i++) PutInt(0, top[i]); Send(0); return 0; } else { for (int j = 1; j < numberOfNodes; j++) { if (j*rows >= height) break; Receive(j); result += GetLL(j); last = 0; for (int i = 0; i < width; i++){ bottom[i] = GetInt(j); if (top[i] > 0 && bottom[i] > 0) { b_top = top[i]; b_bottom = bottom[i]; tmp_result = b_top * b_bottom; for (int k = 1; k <= last; k++) { if (b_bottom >= bottom[i-k]) { if (b_top >= top[i-k]) { tmp_result += cache[i-k]; break; } else { b_bottom = bottom[i-k]; tmp_result += b_top * b_bottom; } } else { if (b_top >= top[i-k]) { b_top = top[i-k]; tmp_result += b_top * b_bottom; } else { tmp_result += b_top * b_bottom; } } } result += tmp_result; cache[i] = tmp_result; last++; } else { cache[i] = 0; last = 0; } } max_rows = min((j + 1) * rows, height) - j * rows; for (int i = 0; i < width; i++) { value = GetInt(j); if (value == max_rows) top[i] += value; else top[i] = value; } } } cout << result << endl; return 0; } |