// PA2017, Krazki 2 // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <algorithm> #include "message.h" #include "krazki.h" using namespace std; #define MASTER_NODE 0 long long cutPoint(long long i, long long N, long long M) { return i*(N/M)+min(i, N%M); } int main() { long long N=PipeHeight(); long long M=NumberOfDiscs(); long long nodes=NumberOfNodes(); long long my_id=MyNodeId(); // nodes=min(min(nodes, N), M); // if (my_id>=nodes) return 0; long long first1 = cutPoint(my_id, N, nodes); long long last1 = cutPoint(my_id+1, N, nodes); long long first2 = cutPoint(my_id, M, nodes); long long last2 = cutPoint(my_id+1, M, nodes); long long myN = last1-first1; long long myM = last2-first2; long long myMinHole=2000000000000000000LL; for (long long i=first1; i<last1; i++) { myMinHole=min(myMinHole, HoleDiameter(i+1)); } for (int i=0; i<nodes; i++) { PutLL(i, last1); PutLL(i, myMinHole); Send(i); } vector<pair<long long, long long> > V; myMinHole=2000000000000000000LL; V.push_back(make_pair(myMinHole, 0LL)); for (int i=0; i<nodes; i++) { Receive(i); long long x=GetLL(i); long long y=GetLL(i); myMinHole=min(myMinHole, y); V.push_back(make_pair(myMinHole, x)); } long long myMaxDisc=0LL; for (long long i=first2; i<last2; i++) { myMaxDisc=max(myMaxDisc, DiscDiameter(i+1)); } int hIdx=0; while(hIdx<V.size() && V[hIdx].first>=myMaxDisc) hIdx++; hIdx--; first1 = cutPoint(hIdx, N, nodes); last1 = cutPoint(hIdx+1, N, nodes); myN = last1-first1 + myM; last1 = min(N, first1+myN); myN = last1-first1; vector<long long> rurka; myMinHole=2000000000000000000LL; for (long long i=first1; i<last1; i++) { myMinHole=min(myMinHole, HoleDiameter(i+1)); rurka.push_back(myMinHole); } vector<long long> krazki; for (;first2<last2; first2++) { while (rurka.size() && rurka.back() < DiscDiameter(first2+1)) rurka.pop_back(); if (!rurka.size()) break; rurka.pop_back(); } PutLL(0, rurka.size() - (M - first2)+first1); Send(0); if (my_id == 0) { long long res = 2000000000000000000LL; for (int i=0; i<nodes; i++){ Receive(i); res=min(res, GetLL(i)); } printf("%lld", max(0LL, res+1)); } 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 | // PA2017, Krazki 2 // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <algorithm> #include "message.h" #include "krazki.h" using namespace std; #define MASTER_NODE 0 long long cutPoint(long long i, long long N, long long M) { return i*(N/M)+min(i, N%M); } int main() { long long N=PipeHeight(); long long M=NumberOfDiscs(); long long nodes=NumberOfNodes(); long long my_id=MyNodeId(); // nodes=min(min(nodes, N), M); // if (my_id>=nodes) return 0; long long first1 = cutPoint(my_id, N, nodes); long long last1 = cutPoint(my_id+1, N, nodes); long long first2 = cutPoint(my_id, M, nodes); long long last2 = cutPoint(my_id+1, M, nodes); long long myN = last1-first1; long long myM = last2-first2; long long myMinHole=2000000000000000000LL; for (long long i=first1; i<last1; i++) { myMinHole=min(myMinHole, HoleDiameter(i+1)); } for (int i=0; i<nodes; i++) { PutLL(i, last1); PutLL(i, myMinHole); Send(i); } vector<pair<long long, long long> > V; myMinHole=2000000000000000000LL; V.push_back(make_pair(myMinHole, 0LL)); for (int i=0; i<nodes; i++) { Receive(i); long long x=GetLL(i); long long y=GetLL(i); myMinHole=min(myMinHole, y); V.push_back(make_pair(myMinHole, x)); } long long myMaxDisc=0LL; for (long long i=first2; i<last2; i++) { myMaxDisc=max(myMaxDisc, DiscDiameter(i+1)); } int hIdx=0; while(hIdx<V.size() && V[hIdx].first>=myMaxDisc) hIdx++; hIdx--; first1 = cutPoint(hIdx, N, nodes); last1 = cutPoint(hIdx+1, N, nodes); myN = last1-first1 + myM; last1 = min(N, first1+myN); myN = last1-first1; vector<long long> rurka; myMinHole=2000000000000000000LL; for (long long i=first1; i<last1; i++) { myMinHole=min(myMinHole, HoleDiameter(i+1)); rurka.push_back(myMinHole); } vector<long long> krazki; for (;first2<last2; first2++) { while (rurka.size() && rurka.back() < DiscDiameter(first2+1)) rurka.pop_back(); if (!rurka.size()) break; rurka.pop_back(); } PutLL(0, rurka.size() - (M - first2)+first1); Send(0); if (my_id == 0) { long long res = 2000000000000000000LL; for (int i=0; i<nodes; i++){ Receive(i); res=min(res, GetLL(i)); } printf("%lld", max(0LL, res+1)); } return 0; } |