#include "kanapka.h" #include "message.h" #include <iostream> #include <cinttypes> #include <limits> #define _DEBUG #ifdef _DEBUG #define DEBUG_START() std::cerr << "(" << MyNodeId() << ")" #define DEBUG_END() << "\n" #define DEBUG_ONE(x) " " #x " ---> " << (x) #define DEBUG1(x) DEBUG_START() DEBUG_ONE(x) DEBUG_END(); #define DEBUG2(x, y) DEBUG_START() DEBUG_ONE(x) << DEBUG_ONE(y) DEBUG_END(); #else #define DEBUG1(x) #define DEBUG2(x, y) #endif int main() { long long int parts = GetN(); int numberOfNodes = NumberOfNodes(); long long int partSize = (parts + numberOfNodes - 1) / numberOfNodes; long long int instanceBegin = MyNodeId() * partSize; long long int instanceEnd = std::min(instanceBegin + partSize, parts); DEBUG2(instanceBegin, instanceEnd); long long int instanceMinSum = std::numeric_limits<long long int>::max(); long long int instanceMinSumTillNow = instanceMinSum; long long int instanceSum = 0; long long int instanceMinPrefixesSums = instanceSum; for (long long int part = instanceBegin; part < instanceEnd; ++part) { long long int taste = GetTaste(part); instanceSum += taste; instanceMinPrefixesSums = std::min(instanceMinPrefixesSums, instanceSum); if (instanceMinSumTillNow > 0) { instanceMinSumTillNow = taste; } else { instanceMinSumTillNow += taste; } instanceMinSum = std::min(instanceMinSum, instanceMinSumTillNow); } if (MyNodeId() < numberOfNodes - 1) { PutLL(numberOfNodes - 1, instanceSum); PutLL(numberOfNodes - 1, instanceMinPrefixesSums); PutLL(numberOfNodes - 1, instanceMinSumTillNow); PutLL(numberOfNodes - 1, instanceMinSum); Send(numberOfNodes - 1); } else { for (int i = numberOfNodes - 2; i >= 0; --i) { Receive(i); long long int remoteSum = GetLL(i); long long int remoteMinPrefixesSums = GetLL(i); long long int remoteMinSumTillNow = GetLL(i); long long int remoteMinSum = GetLL(i); instanceMinSum = std::min(std::min(instanceMinSum, remoteMinSum), instanceMinPrefixesSums + remoteMinSumTillNow); instanceSum += remoteSum; instanceMinPrefixesSums = std::min(remoteMinPrefixesSums, remoteSum + instanceMinPrefixesSums); } std::cout << instanceSum - instanceMinSum << "\n"; } }
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 | #include "kanapka.h" #include "message.h" #include <iostream> #include <cinttypes> #include <limits> #define _DEBUG #ifdef _DEBUG #define DEBUG_START() std::cerr << "(" << MyNodeId() << ")" #define DEBUG_END() << "\n" #define DEBUG_ONE(x) " " #x " ---> " << (x) #define DEBUG1(x) DEBUG_START() DEBUG_ONE(x) DEBUG_END(); #define DEBUG2(x, y) DEBUG_START() DEBUG_ONE(x) << DEBUG_ONE(y) DEBUG_END(); #else #define DEBUG1(x) #define DEBUG2(x, y) #endif int main() { long long int parts = GetN(); int numberOfNodes = NumberOfNodes(); long long int partSize = (parts + numberOfNodes - 1) / numberOfNodes; long long int instanceBegin = MyNodeId() * partSize; long long int instanceEnd = std::min(instanceBegin + partSize, parts); DEBUG2(instanceBegin, instanceEnd); long long int instanceMinSum = std::numeric_limits<long long int>::max(); long long int instanceMinSumTillNow = instanceMinSum; long long int instanceSum = 0; long long int instanceMinPrefixesSums = instanceSum; for (long long int part = instanceBegin; part < instanceEnd; ++part) { long long int taste = GetTaste(part); instanceSum += taste; instanceMinPrefixesSums = std::min(instanceMinPrefixesSums, instanceSum); if (instanceMinSumTillNow > 0) { instanceMinSumTillNow = taste; } else { instanceMinSumTillNow += taste; } instanceMinSum = std::min(instanceMinSum, instanceMinSumTillNow); } if (MyNodeId() < numberOfNodes - 1) { PutLL(numberOfNodes - 1, instanceSum); PutLL(numberOfNodes - 1, instanceMinPrefixesSums); PutLL(numberOfNodes - 1, instanceMinSumTillNow); PutLL(numberOfNodes - 1, instanceMinSum); Send(numberOfNodes - 1); } else { for (int i = numberOfNodes - 2; i >= 0; --i) { Receive(i); long long int remoteSum = GetLL(i); long long int remoteMinPrefixesSums = GetLL(i); long long int remoteMinSumTillNow = GetLL(i); long long int remoteMinSum = GetLL(i); instanceMinSum = std::min(std::min(instanceMinSum, remoteMinSum), instanceMinPrefixesSums + remoteMinSumTillNow); instanceSum += remoteSum; instanceMinPrefixesSums = std::min(remoteMinPrefixesSums, remoteSum + instanceMinPrefixesSums); } std::cout << instanceSum - instanceMinSum << "\n"; } } |