#include "message.h" #include "kanapka.h" #include <iostream> #include <algorithm> using namespace std; struct res { long long total; long long max_l; long long max_r; long long max_index_l; long long max_index_r; }; int main() { long long N = GetN(); long long numberOfWorkers = min(N, (long long)NumberOfNodes()-1); long long work_set = N / numberOfWorkers; long long total = 0; long long max_l = 0; long long max_r = 0; long long max_index_l = -1; long long max_index_r = -1; if(MyNodeId() > N) { return 0; } //cerr << "N:" << N << " N%numberOfWorkers=" << N%numberOfWorkers << " work_set = " << work_set << endl; if(MyNodeId()) { //slaves long long poczatek = (MyNodeId()-1) * work_set + ((MyNodeId() - 1 < N%numberOfWorkers) ? (MyNodeId() - 1) : (N%numberOfWorkers)); long long koniec = poczatek + work_set + (MyNodeId() - 1 < N%numberOfWorkers ? 1 : 0); //cerr << "zakres: <" << poczatek << ", " << koniec << ")" << endl; //left to right for(long long i = poczatek; i < koniec; ++i) { //cerr << "N=" << N << ", i=" << i << endl; long long item = GetTaste(i); total += item; if(total > max_l) { max_l=total; max_index_l=i; } } //right to left total = 0; for(long long i = koniec - 1; i >= poczatek; --i) { long long item = GetTaste(i); total += item; if(total > max_r) { max_r=total; max_index_r=i; } } //cerr << "total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl; PutLL(0, total); PutLL(0, max_l); PutLL(0, max_index_l); PutLL(0, max_r); PutLL(0, max_index_r); Send(0); } else { //master res * results = new res[numberOfWorkers]; total = 0; max_l = 0; for (int i = 0; i < numberOfWorkers; i++) { Receive(i + 1); results[i].total = GetLL(i + 1); results[i].max_l = GetLL(i + 1); results[i].max_index_l = GetLL(i + 1); results[i].max_r = GetLL(i + 1); results[i].max_index_r = GetLL(i + 1); //left if(results[i].max_l + total > max_l) { //cerr << i << ": total=" << results[i].total << " max_l=" << results[i].max_l << endl; max_l=results[i].max_l + total; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; max_index_l=i; } total+=results[i].total; //cerr << i + 1 << ": total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl; } if(max_index_l < 0) { max_l = 0; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; } //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; //right total = 0; for (int i = numberOfWorkers-1; i > max_index_l; i--) { if(results[i].max_r + total > max_r) { //cerr << i << ": total=" << results[i].total << " max_r=" << results[i].max_r << endl; max_r=results[i].max_r + total; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; max_index_r=i; } total+=results[i].total; //cerr << i + 1 << ": total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl; } if(max_index_r < 0) { max_r = 0; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; } //last right worker: if(max_index_r - max_index_l == 1) { if(results[max_index_l].max_r + total > max_r) { max_r=results[max_index_l].max_r + total; } } cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; cout << max_l + max_r << endl; } }
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 | #include "message.h" #include "kanapka.h" #include <iostream> #include <algorithm> using namespace std; struct res { long long total; long long max_l; long long max_r; long long max_index_l; long long max_index_r; }; int main() { long long N = GetN(); long long numberOfWorkers = min(N, (long long)NumberOfNodes()-1); long long work_set = N / numberOfWorkers; long long total = 0; long long max_l = 0; long long max_r = 0; long long max_index_l = -1; long long max_index_r = -1; if(MyNodeId() > N) { return 0; } //cerr << "N:" << N << " N%numberOfWorkers=" << N%numberOfWorkers << " work_set = " << work_set << endl; if(MyNodeId()) { //slaves long long poczatek = (MyNodeId()-1) * work_set + ((MyNodeId() - 1 < N%numberOfWorkers) ? (MyNodeId() - 1) : (N%numberOfWorkers)); long long koniec = poczatek + work_set + (MyNodeId() - 1 < N%numberOfWorkers ? 1 : 0); //cerr << "zakres: <" << poczatek << ", " << koniec << ")" << endl; //left to right for(long long i = poczatek; i < koniec; ++i) { //cerr << "N=" << N << ", i=" << i << endl; long long item = GetTaste(i); total += item; if(total > max_l) { max_l=total; max_index_l=i; } } //right to left total = 0; for(long long i = koniec - 1; i >= poczatek; --i) { long long item = GetTaste(i); total += item; if(total > max_r) { max_r=total; max_index_r=i; } } //cerr << "total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl; PutLL(0, total); PutLL(0, max_l); PutLL(0, max_index_l); PutLL(0, max_r); PutLL(0, max_index_r); Send(0); } else { //master res * results = new res[numberOfWorkers]; total = 0; max_l = 0; for (int i = 0; i < numberOfWorkers; i++) { Receive(i + 1); results[i].total = GetLL(i + 1); results[i].max_l = GetLL(i + 1); results[i].max_index_l = GetLL(i + 1); results[i].max_r = GetLL(i + 1); results[i].max_index_r = GetLL(i + 1); //left if(results[i].max_l + total > max_l) { //cerr << i << ": total=" << results[i].total << " max_l=" << results[i].max_l << endl; max_l=results[i].max_l + total; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; max_index_l=i; } total+=results[i].total; //cerr << i + 1 << ": total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl; } if(max_index_l < 0) { max_l = 0; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; } //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; //right total = 0; for (int i = numberOfWorkers-1; i > max_index_l; i--) { if(results[i].max_r + total > max_r) { //cerr << i << ": total=" << results[i].total << " max_r=" << results[i].max_r << endl; max_r=results[i].max_r + total; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; max_index_r=i; } total+=results[i].total; //cerr << i + 1 << ": total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl; } if(max_index_r < 0) { max_r = 0; //cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; } //last right worker: if(max_index_r - max_index_l == 1) { if(results[max_index_l].max_r + total > max_r) { max_r=results[max_index_l].max_r + total; } } cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl; cout << max_l + max_r << endl; } } |