#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <string.h> #include "poszukiwania.h" #include "message.h" /* PA-2015 R4 */ /* Korzystałem z kodu zaczęrpniętego z książki Piotr Stańczyka "Algorytmika Praktyczna" - kmp */ /* This is brute force, please do not expect much :) */ using namespace std; typedef vector<int> VI; typedef 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 <algorithm> #include <iostream> using namespace std; void KMP(int* str, int strlen, int* wzo, int wzolen, void (*fun)(int)) { #define KMPH(z) while(k > 0 && wzo[k] != z[q]) k = p[k]; if(wzo[k] == z[q]) k++; int p[wzolen + 1], k = 0, q, m; p[1] = 0; for (q = 1; wzo[q] >= 0; q++) { KMPH(wzo); p[q + 1] = k; } m = q; k = 0; for (q = 0; str[q] >= 0; q++) { KMPH(str); if(m == k) { fun(q - m + 1); k = p[k]; } } } long long res = 0; void action(int x) { res++; } #define MMM 12000000 int str[MMM + 1]; int wzo[MMM + 1]; int main() { long long Mlen = SeqLength(); long long Slen = SignalLength(); if(Mlen < 100000) { //ONE instance if (MyNodeId() == 0) { for(int i=1; i<=Mlen; i++) { str[i-1] = SeqAt(i); } str[Mlen] = -1; for(int i=1; i<=Slen; i++) { wzo[i-1] = SignalAt(i); } wzo[Slen] = -1; KMP(str, Mlen, wzo, Slen, action); printf("%lld\n", res); } } else { LL active = NumberOfNodes() - 1; LL block_size = Mlen / active; // if(Slen < block_size || 1) if((Slen < MMM) && (block_size + Slen -1 < MMM)) { //Distributed if(MyNodeId() != 0) { LL begin = ((LL)(MyNodeId() - 1)) * block_size; LL end = ((LL)MyNodeId() * block_size) +(LL)(Slen - 1); if(end > (LL)Mlen) { end = Mlen; } int cnt = 0; for(LL i = begin; i < end; i++) { str[cnt++] = SeqAt(i + 1); } str[cnt] = -1; for(LL i=1; i<=Slen; i++) { wzo[i-1] = SignalAt(i); } wzo[Slen] = -1; KMP(str, cnt, wzo, Slen, action); PutLL(0, res); Send(0); } else { LL sum = 0LL; for(int i = 1; i < NumberOfNodes(); i++) { Receive(i); sum += GetLL(i); } printf("%lld\n", sum); } } else { //Nothing if (MyNodeId() == 0) { printf("%d\n", 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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 | #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <string.h> #include "poszukiwania.h" #include "message.h" /* PA-2015 R4 */ /* Korzystałem z kodu zaczęrpniętego z książki Piotr Stańczyka "Algorytmika Praktyczna" - kmp */ /* This is brute force, please do not expect much :) */ using namespace std; typedef vector<int> VI; typedef 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 <algorithm> #include <iostream> using namespace std; void KMP(int* str, int strlen, int* wzo, int wzolen, void (*fun)(int)) { #define KMPH(z) while(k > 0 && wzo[k] != z[q]) k = p[k]; if(wzo[k] == z[q]) k++; int p[wzolen + 1], k = 0, q, m; p[1] = 0; for (q = 1; wzo[q] >= 0; q++) { KMPH(wzo); p[q + 1] = k; } m = q; k = 0; for (q = 0; str[q] >= 0; q++) { KMPH(str); if(m == k) { fun(q - m + 1); k = p[k]; } } } long long res = 0; void action(int x) { res++; } #define MMM 12000000 int str[MMM + 1]; int wzo[MMM + 1]; int main() { long long Mlen = SeqLength(); long long Slen = SignalLength(); if(Mlen < 100000) { //ONE instance if (MyNodeId() == 0) { for(int i=1; i<=Mlen; i++) { str[i-1] = SeqAt(i); } str[Mlen] = -1; for(int i=1; i<=Slen; i++) { wzo[i-1] = SignalAt(i); } wzo[Slen] = -1; KMP(str, Mlen, wzo, Slen, action); printf("%lld\n", res); } } else { LL active = NumberOfNodes() - 1; LL block_size = Mlen / active; // if(Slen < block_size || 1) if((Slen < MMM) && (block_size + Slen -1 < MMM)) { //Distributed if(MyNodeId() != 0) { LL begin = ((LL)(MyNodeId() - 1)) * block_size; LL end = ((LL)MyNodeId() * block_size) +(LL)(Slen - 1); if(end > (LL)Mlen) { end = Mlen; } int cnt = 0; for(LL i = begin; i < end; i++) { str[cnt++] = SeqAt(i + 1); } str[cnt] = -1; for(LL i=1; i<=Slen; i++) { wzo[i-1] = SignalAt(i); } wzo[Slen] = -1; KMP(str, cnt, wzo, Slen, action); PutLL(0, res); Send(0); } else { LL sum = 0LL; for(int i = 1; i < NumberOfNodes(); i++) { Receive(i); sum += GetLL(i); } printf("%lld\n", sum); } } else { //Nothing if (MyNodeId() == 0) { printf("%d\n", 0); } } } return 0; } |