#ifndef DEBUG_MODE #define NDEBUG #endif #include "message.h" #include "poszukiwania.h" #include <stdio.h> #include <assert.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; #ifdef DEBUG_MODE #define dprint printf #else #define dprint(...) #endif static ll sig_size = 0, seq_size = 0; static ll seg_end = 0, seg_start = 0, seg_search_end = 0; void precomputeSignal(vector<int> &out) { for(int q = 2, k = 0; q <= (int)sig_size; q++) { while(k > 0 && SignalAt(k + 1) != SignalAt(q)) k = out[k]; if(SignalAt(k + 1) == SignalAt(q)) k++; out[q] = k; } } ll find(vector<int> &buffer) { precomputeSignal(buffer); ll out = 0; ll m = sig_size, n = seg_end; for(ll i = seg_start + 1, q = 0; i <= n; i++) { while(q > 0 && SignalAt(q + 1) != SeqAt(i)) q = buffer[q]; if(SignalAt(q + 1) == SeqAt(i)) q++; if(q == m) { if(i - m >= seg_search_end) break; out++; q = buffer[q]; } } return out; } ll brute() { ll out = 0; for(ll j = 0, max = SeqLength() - SignalLength() + 1; j < max; j++) { bool error = false; for(ll i = 0; i < SignalLength(); i++) if(SignalAt(i + 1) != SeqAt(j + i + 1)) { error = true; break; } if(!error) out++; } return out; } int main() { #ifdef DEBUG_MODE Init(); #endif // Let's hope the rest of the signal won't matter :D sig_size = std::min(SignalLength(), 20000500ll); seq_size = SeqLength(); bool run_single = seq_size < NumberOfNodes() * 10; if(run_single) { if(MyNodeId() == 0) { vector<int> buffer(sig_size + 1); seg_start = 0; seg_end = seg_search_end = seq_size; ll count = find(buffer); printf("%lld\n", count); // dprint("brute: %lld\n", brute()); } return 0; } ll part_size = (seq_size + NumberOfNodes() - 1) / NumberOfNodes(); seg_start = part_size * MyNodeId(); seg_search_end = std::min((MyNodeId() + 1) * part_size, seq_size); seg_end = std::min((MyNodeId() + 1) * part_size + sig_size, seq_size); dprint("Node %d/%d: %lld - %lld\n", MyNodeId(), NumberOfNodes(), seg_start, seg_end); vector<int> buffer(sig_size + 1); ll count = find(buffer); if(MyNodeId() == 0) { for(int i = 1; i < NumberOfNodes(); i++) { Receive(i); count += GetLL(i); } printf("%lld\n", count); // dprint("brute: %lld\n", brute()); } else { PutLL(0, count); Send(0); } 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 112 113 114 115 116 117 | #ifndef DEBUG_MODE #define NDEBUG #endif #include "message.h" #include "poszukiwania.h" #include <stdio.h> #include <assert.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; #ifdef DEBUG_MODE #define dprint printf #else #define dprint(...) #endif static ll sig_size = 0, seq_size = 0; static ll seg_end = 0, seg_start = 0, seg_search_end = 0; void precomputeSignal(vector<int> &out) { for(int q = 2, k = 0; q <= (int)sig_size; q++) { while(k > 0 && SignalAt(k + 1) != SignalAt(q)) k = out[k]; if(SignalAt(k + 1) == SignalAt(q)) k++; out[q] = k; } } ll find(vector<int> &buffer) { precomputeSignal(buffer); ll out = 0; ll m = sig_size, n = seg_end; for(ll i = seg_start + 1, q = 0; i <= n; i++) { while(q > 0 && SignalAt(q + 1) != SeqAt(i)) q = buffer[q]; if(SignalAt(q + 1) == SeqAt(i)) q++; if(q == m) { if(i - m >= seg_search_end) break; out++; q = buffer[q]; } } return out; } ll brute() { ll out = 0; for(ll j = 0, max = SeqLength() - SignalLength() + 1; j < max; j++) { bool error = false; for(ll i = 0; i < SignalLength(); i++) if(SignalAt(i + 1) != SeqAt(j + i + 1)) { error = true; break; } if(!error) out++; } return out; } int main() { #ifdef DEBUG_MODE Init(); #endif // Let's hope the rest of the signal won't matter :D sig_size = std::min(SignalLength(), 20000500ll); seq_size = SeqLength(); bool run_single = seq_size < NumberOfNodes() * 10; if(run_single) { if(MyNodeId() == 0) { vector<int> buffer(sig_size + 1); seg_start = 0; seg_end = seg_search_end = seq_size; ll count = find(buffer); printf("%lld\n", count); // dprint("brute: %lld\n", brute()); } return 0; } ll part_size = (seq_size + NumberOfNodes() - 1) / NumberOfNodes(); seg_start = part_size * MyNodeId(); seg_search_end = std::min((MyNodeId() + 1) * part_size, seq_size); seg_end = std::min((MyNodeId() + 1) * part_size + sig_size, seq_size); dprint("Node %d/%d: %lld - %lld\n", MyNodeId(), NumberOfNodes(), seg_start, seg_end); vector<int> buffer(sig_size + 1); ll count = find(buffer); if(MyNodeId() == 0) { for(int i = 1; i < NumberOfNodes(); i++) { Receive(i); count += GetLL(i); } printf("%lld\n", count); // dprint("brute: %lld\n", brute()); } else { PutLL(0, count); Send(0); } return 0; } |