#include "kanapka.h" #include "message.h" #include <cstdio> const int MAX_NODES = 1000; struct partial_sum { long long whole; long long max; long long maxn; partial_sum() : whole(0), max(0), maxn(-1) { } partial_sum& operator+=(long long num) { whole += GetTaste(num); if (whole > max) { max = whole; maxn = num; } return *this; } static partial_sum lsum(long long a, long long b) { //fprintf(stderr, "lsum %lld %lld: ", a, b); partial_sum s; for (; a < b; ++a) { s += a; } //fprintf(stderr, " %lld %lld %lld\n", s.whole, s.max, s.maxn); return s; } static partial_sum rsum(long long a, long long b) { //fprintf(stderr, "rsum %lld %lld: ", a, b); partial_sum s; for (; a > b; --a) { s += a; } //fprintf(stderr, " %lld %lld %lld\n", s.whole, s.max, s.maxn); return s; } partial_sum& operator+=(const partial_sum& other) { if (whole+other.max > max) { max = whole+other.max; maxn = other.maxn; } whole += other.whole; } void write(int dst) const { PutLL(dst, whole); PutLL(dst, max); PutLL(dst, maxn); Send(dst); } static partial_sum read(int src) { partial_sum s; Receive(src); s.whole = GetLL(src); s.max = GetLL(src); s.maxn = GetLL(src); return s; } }; int main() { partial_sum lsum, rsum; const long long partition = GetN()/NumberOfNodes(); if (MyNodeId() == NumberOfNodes()-1) lsum = partial_sum::lsum(partition*MyNodeId(), GetN()); else lsum = partial_sum::lsum(partition*MyNodeId(), partition*(MyNodeId()+1)); if (MyNodeId() == 0) { for (int i = 1; i < NumberOfNodes(); ++i) { lsum += partial_sum::read(i); } for (int i = 1; i < NumberOfNodes(); ++i) { PutLL(i, lsum.maxn); Send(i); } const long long rpart = (GetN()-lsum.maxn-1)/NumberOfNodes(); rsum = partial_sum::rsum(GetN()-1, GetN()-rpart*(MyNodeId()+1)-1); for (int i = 1; i < NumberOfNodes(); ++i) { rsum += partial_sum::read(i); } printf("%lld\n", lsum.max+rsum.max); } else { lsum.write(0); Receive(0); const long long maxl = GetLL(0); const long long rpart = (GetN()-maxl-1)/NumberOfNodes(); if (MyNodeId() == NumberOfNodes()-1) rsum = partial_sum::rsum(GetN()-rpart*MyNodeId()-1, maxl); else rsum = partial_sum::rsum(GetN()-rpart*MyNodeId()-1, GetN()-rpart*(MyNodeId()+1)-1); rsum.write(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 | #include "kanapka.h" #include "message.h" #include <cstdio> const int MAX_NODES = 1000; struct partial_sum { long long whole; long long max; long long maxn; partial_sum() : whole(0), max(0), maxn(-1) { } partial_sum& operator+=(long long num) { whole += GetTaste(num); if (whole > max) { max = whole; maxn = num; } return *this; } static partial_sum lsum(long long a, long long b) { //fprintf(stderr, "lsum %lld %lld: ", a, b); partial_sum s; for (; a < b; ++a) { s += a; } //fprintf(stderr, " %lld %lld %lld\n", s.whole, s.max, s.maxn); return s; } static partial_sum rsum(long long a, long long b) { //fprintf(stderr, "rsum %lld %lld: ", a, b); partial_sum s; for (; a > b; --a) { s += a; } //fprintf(stderr, " %lld %lld %lld\n", s.whole, s.max, s.maxn); return s; } partial_sum& operator+=(const partial_sum& other) { if (whole+other.max > max) { max = whole+other.max; maxn = other.maxn; } whole += other.whole; } void write(int dst) const { PutLL(dst, whole); PutLL(dst, max); PutLL(dst, maxn); Send(dst); } static partial_sum read(int src) { partial_sum s; Receive(src); s.whole = GetLL(src); s.max = GetLL(src); s.maxn = GetLL(src); return s; } }; int main() { partial_sum lsum, rsum; const long long partition = GetN()/NumberOfNodes(); if (MyNodeId() == NumberOfNodes()-1) lsum = partial_sum::lsum(partition*MyNodeId(), GetN()); else lsum = partial_sum::lsum(partition*MyNodeId(), partition*(MyNodeId()+1)); if (MyNodeId() == 0) { for (int i = 1; i < NumberOfNodes(); ++i) { lsum += partial_sum::read(i); } for (int i = 1; i < NumberOfNodes(); ++i) { PutLL(i, lsum.maxn); Send(i); } const long long rpart = (GetN()-lsum.maxn-1)/NumberOfNodes(); rsum = partial_sum::rsum(GetN()-1, GetN()-rpart*(MyNodeId()+1)-1); for (int i = 1; i < NumberOfNodes(); ++i) { rsum += partial_sum::read(i); } printf("%lld\n", lsum.max+rsum.max); } else { lsum.write(0); Receive(0); const long long maxl = GetLL(0); const long long rpart = (GetN()-maxl-1)/NumberOfNodes(); if (MyNodeId() == NumberOfNodes()-1) rsum = partial_sum::rsum(GetN()-rpart*MyNodeId()-1, maxl); else rsum = partial_sum::rsum(GetN()-rpart*MyNodeId()-1, GetN()-rpart*(MyNodeId()+1)-1); rsum.write(0); } } |