#include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <cmath> #include <vector> using namespace std; int main() { std::ios::sync_with_stdio(false); long long M = SeqLength(); long long S = SignalLength(); long long partsNum = ceil(M/NumberOfNodes()); long long partBegin = partsNum*MyNodeId(); long long partEnd = partsNum*(MyNodeId()+1); long long partLen = partEnd-partBegin; if (NumberOfNodes() > S) { partBegin = 0; partEnd = M; partLen = M; if (MyNodeId() > 0) { PutLL(0, 0); Send(0); return 0; } } vector<int> T(S+1, -1); for (int i = 1; i <= S; ++i) { int pos = T[i-1]; while (pos != -1 && SignalAt(pos+1) != SignalAt(i)) pos = T[pos]; T[i] = pos + 1; } int sp = partBegin; int kp = 0; long long localResult = 0; while (sp < min(partEnd+S-1,M)) { while (kp != -1 && (kp == S || SignalAt(kp+1) != SeqAt(sp+1))) kp = T[kp]; kp++; sp++; if (kp == S) { localResult++; } } if (MyNodeId() == 0) { long long result = localResult; for (int i = 1; i < NumberOfNodes(); ++i) { int inst = Receive(-1); result += GetLL(inst); } cout << result << endl; } else { PutLL(0, localResult); Send(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 | #include "poszukiwania.h" #include "message.h" #include <algorithm> #include <iostream> #include <cmath> #include <vector> using namespace std; int main() { std::ios::sync_with_stdio(false); long long M = SeqLength(); long long S = SignalLength(); long long partsNum = ceil(M/NumberOfNodes()); long long partBegin = partsNum*MyNodeId(); long long partEnd = partsNum*(MyNodeId()+1); long long partLen = partEnd-partBegin; if (NumberOfNodes() > S) { partBegin = 0; partEnd = M; partLen = M; if (MyNodeId() > 0) { PutLL(0, 0); Send(0); return 0; } } vector<int> T(S+1, -1); for (int i = 1; i <= S; ++i) { int pos = T[i-1]; while (pos != -1 && SignalAt(pos+1) != SignalAt(i)) pos = T[pos]; T[i] = pos + 1; } int sp = partBegin; int kp = 0; long long localResult = 0; while (sp < min(partEnd+S-1,M)) { while (kp != -1 && (kp == S || SignalAt(kp+1) != SeqAt(sp+1))) kp = T[kp]; kp++; sp++; if (kp == S) { localResult++; } } if (MyNodeId() == 0) { long long result = localResult; for (int i = 1; i < NumberOfNodes(); ++i) { int inst = Receive(-1); result += GetLL(inst); } cout << result << endl; } else { PutLL(0, localResult); Send(0); } } |