#include "message.h" #if 1 #include "poszukiwania.h" #elif 0 #include "poszukiwania-test.h" #elif 0 #include "poszukiwania-t.h" #endif #include <cstdio> using namespace std; typedef unsigned int u32; typedef unsigned long long u64; typedef signed long long i64; const int INF = 0x7fffffff; #define min(a,b) (((a)<(b))?(a):(b)) #define fprintf(...) u32 S; u32 M; int id; int calculate(u32 b, u32 e) { fprintf(stderr, "[%d] calculate(b=%u, e=%u)\n", id, b, e); if(e > ((M+1)-S)) e = (M+1)-S; if(e <= b) return 0; int *s = new int[S]; int *m = new int[S+(e-b)+2]; int *sptr = s; int *mptr = m; for(u32 i=0; i<S ;++i) *sptr++ = SignalAt(i+1); for(u32 i=b; i<(e+S-1); i++) *mptr++ = SeqAt(i+1); int result = 0; e-=b; for(u32 a=0; a<e; a++) { for(u32 i=0; i<S ;++i) if(s[i]!=m[i+a]) goto _next; ++result; _next: ; } return result; } void master() { int nodes = NumberOfNodes(); int result = 0; u32 step = (M - S) / nodes + 1; fprintf(stderr, "[%d] master nodes=%d M=%u S=%u step=%u\n", id, nodes, M, S, step); u32 begin = 0; u32 end = step; for(int n=1; n<nodes; ++n) { PutInt(n,begin); PutInt(n,end); Send(n); begin+=step; end+=step; } fprintf(stderr, "[%d] master begin=%u end=%u (to be checked)\n", id, begin, end); end = (M+1)-S; fprintf(stderr, "[%d] master now end=%u\n", id, end); if(begin < end) result = calculate(begin, end); for(int n=1; n<nodes ;++n) { int id = Receive(-1); result += GetInt(id); } printf("%d\n", result); } void slave() { Receive(0); u32 begin = GetInt(0); u32 end = GetInt(0); PutInt(0, calculate(begin, end)); Send(0); } int main() { S = SignalLength(); M = SeqLength(); id = MyNodeId(); fprintf(stderr, "[%d] START\n", id); if(id == 0) master(); else slave(); fprintf(stderr, "[%d] EXIT\n", id); 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 | #include "message.h" #if 1 #include "poszukiwania.h" #elif 0 #include "poszukiwania-test.h" #elif 0 #include "poszukiwania-t.h" #endif #include <cstdio> using namespace std; typedef unsigned int u32; typedef unsigned long long u64; typedef signed long long i64; const int INF = 0x7fffffff; #define min(a,b) (((a)<(b))?(a):(b)) #define fprintf(...) u32 S; u32 M; int id; int calculate(u32 b, u32 e) { fprintf(stderr, "[%d] calculate(b=%u, e=%u)\n", id, b, e); if(e > ((M+1)-S)) e = (M+1)-S; if(e <= b) return 0; int *s = new int[S]; int *m = new int[S+(e-b)+2]; int *sptr = s; int *mptr = m; for(u32 i=0; i<S ;++i) *sptr++ = SignalAt(i+1); for(u32 i=b; i<(e+S-1); i++) *mptr++ = SeqAt(i+1); int result = 0; e-=b; for(u32 a=0; a<e; a++) { for(u32 i=0; i<S ;++i) if(s[i]!=m[i+a]) goto _next; ++result; _next: ; } return result; } void master() { int nodes = NumberOfNodes(); int result = 0; u32 step = (M - S) / nodes + 1; fprintf(stderr, "[%d] master nodes=%d M=%u S=%u step=%u\n", id, nodes, M, S, step); u32 begin = 0; u32 end = step; for(int n=1; n<nodes; ++n) { PutInt(n,begin); PutInt(n,end); Send(n); begin+=step; end+=step; } fprintf(stderr, "[%d] master begin=%u end=%u (to be checked)\n", id, begin, end); end = (M+1)-S; fprintf(stderr, "[%d] master now end=%u\n", id, end); if(begin < end) result = calculate(begin, end); for(int n=1; n<nodes ;++n) { int id = Receive(-1); result += GetInt(id); } printf("%d\n", result); } void slave() { Receive(0); u32 begin = GetInt(0); u32 end = GetInt(0); PutInt(0, calculate(begin, end)); Send(0); } int main() { S = SignalLength(); M = SeqLength(); id = MyNodeId(); fprintf(stderr, "[%d] START\n", id); if(id == 0) master(); else slave(); fprintf(stderr, "[%d] EXIT\n", id); return 0; } |