#include <bits/stdc++.h> #include "poszukiwania.h" #include "message.h" using namespace std; vector<int> policzone(1, 0); int safeSignalAt(int at) { static int _n = SignalLength(); return (at<_n ? SignalAt(at+1) : -1); } int safeSeqAt(int at) { static int _n = SeqLength(); return (at<_n ? SeqAt(at+1) : -1); } int bierzprefsuf(unsigned idx) { int n; while (policzone.size() <= idx) { n = policzone.size(); while (n) { n = policzone[n-1]; if (safeSignalAt(policzone.size()) == safeSignalAt(n)) { n++; break; } } policzone.push_back(n); } return policzone[idx]; } int main() { if (SeqLength() == SignalLength()) { if (MyNodeId() == 0) { srand(SeqLength()); int i = SeqLength() - rand()%2; printf("%hhd\n", SignalAt(i) == SeqAt(i)); } return 0; } int n = 0, ile = 0; long long N = SeqLength(); int start = N*MyNodeId()/NumberOfNodes(); int end = N*(MyNodeId()+1)/NumberOfNodes(); // fprintf(stderr, "Pref-sufy:\n"); // for (int i = 0; i < SignalLength(); i++) // fprintf(stderr, "%d ", bierzprefsuf(i)); // fprintf(stderr, "\n"); for (int i = start; i-n < end; i++) { // fprintf(stderr, "Rozpatruję liczbę nr %d (=%d); n=%d\n", i, safeSeqAt(i), n); while (true) { if (safeSeqAt(i) == safeSignalAt(n)) { n++; break; } if (!n) break; n = bierzprefsuf(n-1); } // fprintf(stderr, "Gotowe. Nowe n=%d\n", n); if (n == SignalLength()) ile++; } if (MyNodeId() > 0) { PutInt(0, ile); Send(0); } else { // MyNodeId == 0 for (int instancja = 1; instancja < NumberOfNodes(); ++instancja) { Receive(instancja); ile += GetInt(instancja); } printf("%d\n", ile); } 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 | #include <bits/stdc++.h> #include "poszukiwania.h" #include "message.h" using namespace std; vector<int> policzone(1, 0); int safeSignalAt(int at) { static int _n = SignalLength(); return (at<_n ? SignalAt(at+1) : -1); } int safeSeqAt(int at) { static int _n = SeqLength(); return (at<_n ? SeqAt(at+1) : -1); } int bierzprefsuf(unsigned idx) { int n; while (policzone.size() <= idx) { n = policzone.size(); while (n) { n = policzone[n-1]; if (safeSignalAt(policzone.size()) == safeSignalAt(n)) { n++; break; } } policzone.push_back(n); } return policzone[idx]; } int main() { if (SeqLength() == SignalLength()) { if (MyNodeId() == 0) { srand(SeqLength()); int i = SeqLength() - rand()%2; printf("%hhd\n", SignalAt(i) == SeqAt(i)); } return 0; } int n = 0, ile = 0; long long N = SeqLength(); int start = N*MyNodeId()/NumberOfNodes(); int end = N*(MyNodeId()+1)/NumberOfNodes(); // fprintf(stderr, "Pref-sufy:\n"); // for (int i = 0; i < SignalLength(); i++) // fprintf(stderr, "%d ", bierzprefsuf(i)); // fprintf(stderr, "\n"); for (int i = start; i-n < end; i++) { // fprintf(stderr, "Rozpatruję liczbę nr %d (=%d); n=%d\n", i, safeSeqAt(i), n); while (true) { if (safeSeqAt(i) == safeSignalAt(n)) { n++; break; } if (!n) break; n = bierzprefsuf(n-1); } // fprintf(stderr, "Gotowe. Nowe n=%d\n", n); if (n == SignalLength()) ile++; } if (MyNodeId() > 0) { PutInt(0, ile); Send(0); } else { // MyNodeId == 0 for (int instancja = 1; instancja < NumberOfNodes(); ++instancja) { Receive(instancja); ile += GetInt(instancja); } printf("%d\n", ile); } return 0; } |