//============================================================================ // Name : kan.cpp // Author : Damian Klata //============================================================================ #include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; int main() { int nodeId = MyNodeId(); int nodes = NumberOfNodes(); long long N = GetN(); /** Definie range of searching for single instance */ if (nodeId >= N) { return 0; } long long size = nodes; if (N < nodes) { size = N; } long long start = nodeId * N / size; long long finish = (nodeId + 1) * N / size; /** Find values for single range */ long long minTaste = 0; long long sumTaste = 0; long long maxTasteL = 0; long long maxTasteR = 0; /** Search divider (part with minimum value) and calculate sum of tastes */ long long divider = 0; long long taste = 0; for (long long i = start; i < finish; i++) { taste = GetTaste(i); sumTaste += taste; if (taste < minTaste) { minTaste = taste; divider = i; } } /** If found divider has value below 0 then find maximum sum of left and right parts */ if (minTaste < 0) { long long sumTasteL = 0; for (long long i = start; i < divider; i++) { taste = GetTaste(i); sumTasteL += taste; if (sumTasteL > maxTasteL) { maxTasteL = sumTasteL; } } long sumTasteR = 0; for (long i = finish - 1; i > divider; i--) { long taste = GetTaste(i); sumTasteR += taste; if (sumTasteR > maxTasteR) { maxTasteR = sumTasteR; } } } if (nodeId > 0) { /** Send result to 0 instance */ PutLL(0, minTaste); PutLL(0, sumTaste); PutLL(0, maxTasteL); PutLL(0, maxTasteR); Send(0); } else { /** For INSTANCE no 0 */ /** Receive partial results */ long long values[size * 4]; values[0] = minTaste; values[1] = sumTaste; values[2] = maxTasteL; values[3] = maxTasteR; for (long long i = 1; i < size; i++) { Receive(i); values[i * 4 + 0] = GetLL(i); values[i * 4 + 1] = GetLL(i); values[i * 4 + 2] = GetLL(i); values[i * 4 + 3] = GetLL(i); } /** Find global divider */ long long insMinimum = 0; long long insDivider = 0; for (long long i = 0; i < size; i++) { long long m = values[i * 4 + 0]; if (m < insMinimum) { insMinimum = m; insDivider = i; } } long long maxSum = 0; if (insMinimum >= 0) { /** Sum of partials sums if divider below 0 not found */ for (long long i = 0; i < size; i++) { long long s = values[i * 4 + 1]; maxSum += s; } } else { /** Find global maximum sum of left chain */ long long maxL = 0; long long sumL = 0; for (long long i = 0; i <= insDivider; i++) { long long s = values[i * 4 + 1]; long long l = values[i * 4 + 2]; if (sumL + l > maxL) { maxL = sumL + l; } if (i < insDivider) { sumL += s; } if (sumL > maxL) { maxL = sumL; } } /** Find global maximum sum of right chain */ long long maxR = 0; long long sumR = 0; for (long long i = size - 1; i >= insDivider; i--) { long long s = values[i * 4 + 1]; long long r = values[i * 4 + 3]; if (sumR + r > maxR) { maxR = sumR + r; } if (i > insDivider) { sumR += s; } if (sumR > maxR) { maxR = sumR; } } maxSum = maxL + maxR; } /** Print result */ cout << maxSum << 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 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 | //============================================================================ // Name : kan.cpp // Author : Damian Klata //============================================================================ #include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; int main() { int nodeId = MyNodeId(); int nodes = NumberOfNodes(); long long N = GetN(); /** Definie range of searching for single instance */ if (nodeId >= N) { return 0; } long long size = nodes; if (N < nodes) { size = N; } long long start = nodeId * N / size; long long finish = (nodeId + 1) * N / size; /** Find values for single range */ long long minTaste = 0; long long sumTaste = 0; long long maxTasteL = 0; long long maxTasteR = 0; /** Search divider (part with minimum value) and calculate sum of tastes */ long long divider = 0; long long taste = 0; for (long long i = start; i < finish; i++) { taste = GetTaste(i); sumTaste += taste; if (taste < minTaste) { minTaste = taste; divider = i; } } /** If found divider has value below 0 then find maximum sum of left and right parts */ if (minTaste < 0) { long long sumTasteL = 0; for (long long i = start; i < divider; i++) { taste = GetTaste(i); sumTasteL += taste; if (sumTasteL > maxTasteL) { maxTasteL = sumTasteL; } } long sumTasteR = 0; for (long i = finish - 1; i > divider; i--) { long taste = GetTaste(i); sumTasteR += taste; if (sumTasteR > maxTasteR) { maxTasteR = sumTasteR; } } } if (nodeId > 0) { /** Send result to 0 instance */ PutLL(0, minTaste); PutLL(0, sumTaste); PutLL(0, maxTasteL); PutLL(0, maxTasteR); Send(0); } else { /** For INSTANCE no 0 */ /** Receive partial results */ long long values[size * 4]; values[0] = minTaste; values[1] = sumTaste; values[2] = maxTasteL; values[3] = maxTasteR; for (long long i = 1; i < size; i++) { Receive(i); values[i * 4 + 0] = GetLL(i); values[i * 4 + 1] = GetLL(i); values[i * 4 + 2] = GetLL(i); values[i * 4 + 3] = GetLL(i); } /** Find global divider */ long long insMinimum = 0; long long insDivider = 0; for (long long i = 0; i < size; i++) { long long m = values[i * 4 + 0]; if (m < insMinimum) { insMinimum = m; insDivider = i; } } long long maxSum = 0; if (insMinimum >= 0) { /** Sum of partials sums if divider below 0 not found */ for (long long i = 0; i < size; i++) { long long s = values[i * 4 + 1]; maxSum += s; } } else { /** Find global maximum sum of left chain */ long long maxL = 0; long long sumL = 0; for (long long i = 0; i <= insDivider; i++) { long long s = values[i * 4 + 1]; long long l = values[i * 4 + 2]; if (sumL + l > maxL) { maxL = sumL + l; } if (i < insDivider) { sumL += s; } if (sumL > maxL) { maxL = sumL; } } /** Find global maximum sum of right chain */ long long maxR = 0; long long sumR = 0; for (long long i = size - 1; i >= insDivider; i--) { long long s = values[i * 4 + 1]; long long r = values[i * 4 + 3]; if (sumR + r > maxR) { maxR = sumR + r; } if (i > insDivider) { sumR += s; } if (sumR > maxR) { maxR = sumR; } } maxSum = maxL + maxR; } /** Print result */ cout << maxSum << endl; } return 0; } |