#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <utility> #include <map> #include <set> using namespace std; typedef vector<int> VI; typedef unsigned long long LL; #define FOR(x, b, e) for (int x = b; x <= (e); ++x) #define FORD(x, b, e) for (int x = b; x >= (e); --x) #define REP(x, n) for (int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second #include "message.h" #include "poszukiwania.h" int FIRST, LAST; LL phash() { LL h = 0; for (int i = 0; i < SignalLength(); i++) { h = h + SignalAt(i + 1); } return h; } LL shash() { LL h = 0; for (int i = FIRST; i < FIRST + SignalLength(); i++) { h = h + SeqAt(i + 1); } return h; } inline LL rollHash(int first, int next, LL hash) { return hash - SeqAt(first + 1) + SeqAt(next + 1); } int main() { FIRST = MyNodeId() * SeqLength() / NumberOfNodes(); LAST = (MyNodeId() + 1) * SeqLength() / NumberOfNodes() - 1; if (FIRST + SignalLength() >= SeqLength()) { PutInt(0, 0); Send(0); return 0; } LL patternHash = phash(); LL hash = shash(); int first = FIRST; int next = first + SignalLength(); VI puts; while (true) { if (patternHash == hash) { bool match = true; REP(i, SignalLength()) { if (SignalAt(i + 1) != SeqAt(i + first + 1)) { match = false; break; } } if (match) puts.PB(first); } if (first > LAST) break; hash = rollHash(first, next, hash); first++; next++; } PutInt(0, puts.size()); FOREACH (i, puts) PutInt(0, *i); Send(0); if (MyNodeId() == 0) { set<int> result; REP(i, NumberOfNodes()) { int source = Receive(i); int count = GetInt(source); REP(j, count) result.insert(GetInt(source)); } printf("%ld\n", result.size()); } 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 | #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <utility> #include <map> #include <set> using namespace std; typedef vector<int> VI; typedef unsigned long long LL; #define FOR(x, b, e) for (int x = b; x <= (e); ++x) #define FORD(x, b, e) for (int x = b; x >= (e); --x) #define REP(x, n) for (int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second #include "message.h" #include "poszukiwania.h" int FIRST, LAST; LL phash() { LL h = 0; for (int i = 0; i < SignalLength(); i++) { h = h + SignalAt(i + 1); } return h; } LL shash() { LL h = 0; for (int i = FIRST; i < FIRST + SignalLength(); i++) { h = h + SeqAt(i + 1); } return h; } inline LL rollHash(int first, int next, LL hash) { return hash - SeqAt(first + 1) + SeqAt(next + 1); } int main() { FIRST = MyNodeId() * SeqLength() / NumberOfNodes(); LAST = (MyNodeId() + 1) * SeqLength() / NumberOfNodes() - 1; if (FIRST + SignalLength() >= SeqLength()) { PutInt(0, 0); Send(0); return 0; } LL patternHash = phash(); LL hash = shash(); int first = FIRST; int next = first + SignalLength(); VI puts; while (true) { if (patternHash == hash) { bool match = true; REP(i, SignalLength()) { if (SignalAt(i + 1) != SeqAt(i + first + 1)) { match = false; break; } } if (match) puts.PB(first); } if (first > LAST) break; hash = rollHash(first, next, hash); first++; next++; } PutInt(0, puts.size()); FOREACH (i, puts) PutInt(0, *i); Send(0); if (MyNodeId() == 0) { set<int> result; REP(i, NumberOfNodes()) { int source = Receive(i); int count = GetInt(source); REP(j, count) result.insert(GetInt(source)); } printf("%ld\n", result.size()); } return 0; } |