#include "poszukiwania.h" #include "message.h" #include <algorithm> #include <cstdio> #define LL long long using namespace std; LL podzial,wynik,help,endP,HASH1,HASH2,NASH1,NASH2,PT,R1,R2,P1,P2,P,G1,G2,RP1,RP2,AA; LL MOD = 1000000007; int node,cNodes; LL H1[1010]; LL PTT(LL x,LL y); bool CompHashes(LL H1,LL S1,LL H2, LL S2,LL P); void PrintHashes(LL H1,LL S1,LL H2, LL S2,LL P); LL MD(LL X){ if(X>=0)return X%MOD; LL Y = X/MOD; if(Y*MOD==X)return 0; Y--; return X-(Y*MOD); } int main() { long long N = SeqLength(); long long M = SignalLength(); node = MyNodeId(); cNodes = NumberOfNodes()-1; podzial = N/cNodes; if(podzial*cNodes<N) ++podzial; if(M>N){ if(node==0)printf("0\n"); return 0; } /*if(node==0 && true==false){ for(LL i=1;i<=N;++i)printf("%lld ",SeqAt(i));printf("\n"); for(LL i=1;i<=M;++i)printf("%lld ",SignalAt(i));printf("\n"); }*/ if(node>0){ help = podzial*(node-1)+1; endP = help+podzial-1; HASH1 = HASH2 = 0; R1 = R2 = 1; for(LL i=help;i<=endP && i<=M;++i){ P = SignalAt(i); P1 = (P*R1)%MOD; R1*=47;R1%= MOD; HASH1 = (HASH1+P1)%MOD; } PutLL(0,HASH1); Send(0); HASH1 = HASH2 = 0; R1 = R2 = 1; for(LL i=help;i<=endP && i<=N;++i){ P = SeqAt(i); P1 = (P*R1)%MOD; R1*=47;R1%= MOD; HASH1 = (HASH1+P1)%MOD; } H1[0] = HASH1; for(int i=1;i<node;++i){ PutLL(i,HASH1); Send(i); } for(int i=node+1;i<=cNodes;++i){ Receive(i); H1[i-node] = GetLL(i); } Receive(0); HASH1 = GetLL(0); R1 = R2 = 1; RP1 = PTT(47,podzial); for(LL i=0;i<M;++i){ if(help+i>N){ PutLL(0,0); Send(0); return 0; } if((help+i-1)%podzial==0 && i+podzial<=M){ AA = ((help+i-1)/podzial)+1-node; NASH1+= H1[AA]*R1; NASH1%= MOD; R1 = (R1*RP1)%MOD; i+= podzial-1; } else{ P = SeqAt(help+i); P1 = (P*R1)%MOD; R1*=47;R1%= MOD; NASH1 = (NASH1+P1)%MOD; } } //printf("%d %lld %lld %lld %lld %lld %lld\n",node,NASH1,HASH1,SeqAt(help),SignalAt(1),SeqAt(help+M-1),SignalAt(M)); if(SeqAt(help)==SignalAt(1) && SeqAt(help+M-1)==SignalAt(M)){ if(CompHashes(NASH1,0,HASH1,0,47)){ ++wynik; //printf("START %lld %d\n",help,node); } } G1 = G2 = 1; for(LL i=help+1;i<=endP;++i){ AA = i+M-1; if(AA>N)break; P = SeqAt(i-1); NASH1-= P*G1; NASH1 = MD(NASH1); P = SeqAt(AA); NASH1 = (NASH1+P*R1)%MOD; G1*=47;G1%= MOD; R1*=47;R1%= MOD; if(SeqAt(i)==SignalAt(1) && P==SignalAt(M)){ if(CompHashes(NASH1,i-help,HASH1,0,47)){ //printf("START %lld %d\n",i,node); ++wynik; } } } //printf("%d %lld\n",node,wynik); PutLL(0,wynik); Send(0); } else{ HASH1 = 0;HASH2 = 0; for(int i=1;i<=cNodes;++i){ Receive(i); help = podzial*(i-1); G1 = GetLL(i); HASH1+= G1*PTT(47,help); HASH1%= MOD; } for(int i=1;i<=cNodes;++i){ PutLL(i,HASH1); Send(i); } for(int i=1;i<=cNodes;++i){ Receive(i); wynik+= GetLL(i); } printf("%lld\n",wynik); } return 0; } LL PTT(LL x,LL y){ LL W = 1; int pt = 1; while(pt<=y){ if(pt&y){ W*=x; W%=MOD; } pt*=2; x*=x; x%=MOD; } return W; } bool CompHashes(LL H1,LL S1,LL H2, LL S2,LL P){ if(S1>S2){ H2*=PTT(P,S1-S2); H2%= MOD; } else if(S1<S2){ H1*=PTT(P,S2-S1); H1%= MOD; } return H1==H2; } void PrintHashes(LL H1,LL S1,LL H2, LL S2,LL P){ if(S1>S2){ H2*=PTT(P,S1-S2); H2%= MOD; } else if(S1<S2){ H1*=PTT(P,S2-S1); H1%= MOD; } printf("%lld %lld\n",H1,H2); }
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 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | #include "poszukiwania.h" #include "message.h" #include <algorithm> #include <cstdio> #define LL long long using namespace std; LL podzial,wynik,help,endP,HASH1,HASH2,NASH1,NASH2,PT,R1,R2,P1,P2,P,G1,G2,RP1,RP2,AA; LL MOD = 1000000007; int node,cNodes; LL H1[1010]; LL PTT(LL x,LL y); bool CompHashes(LL H1,LL S1,LL H2, LL S2,LL P); void PrintHashes(LL H1,LL S1,LL H2, LL S2,LL P); LL MD(LL X){ if(X>=0)return X%MOD; LL Y = X/MOD; if(Y*MOD==X)return 0; Y--; return X-(Y*MOD); } int main() { long long N = SeqLength(); long long M = SignalLength(); node = MyNodeId(); cNodes = NumberOfNodes()-1; podzial = N/cNodes; if(podzial*cNodes<N) ++podzial; if(M>N){ if(node==0)printf("0\n"); return 0; } /*if(node==0 && true==false){ for(LL i=1;i<=N;++i)printf("%lld ",SeqAt(i));printf("\n"); for(LL i=1;i<=M;++i)printf("%lld ",SignalAt(i));printf("\n"); }*/ if(node>0){ help = podzial*(node-1)+1; endP = help+podzial-1; HASH1 = HASH2 = 0; R1 = R2 = 1; for(LL i=help;i<=endP && i<=M;++i){ P = SignalAt(i); P1 = (P*R1)%MOD; R1*=47;R1%= MOD; HASH1 = (HASH1+P1)%MOD; } PutLL(0,HASH1); Send(0); HASH1 = HASH2 = 0; R1 = R2 = 1; for(LL i=help;i<=endP && i<=N;++i){ P = SeqAt(i); P1 = (P*R1)%MOD; R1*=47;R1%= MOD; HASH1 = (HASH1+P1)%MOD; } H1[0] = HASH1; for(int i=1;i<node;++i){ PutLL(i,HASH1); Send(i); } for(int i=node+1;i<=cNodes;++i){ Receive(i); H1[i-node] = GetLL(i); } Receive(0); HASH1 = GetLL(0); R1 = R2 = 1; RP1 = PTT(47,podzial); for(LL i=0;i<M;++i){ if(help+i>N){ PutLL(0,0); Send(0); return 0; } if((help+i-1)%podzial==0 && i+podzial<=M){ AA = ((help+i-1)/podzial)+1-node; NASH1+= H1[AA]*R1; NASH1%= MOD; R1 = (R1*RP1)%MOD; i+= podzial-1; } else{ P = SeqAt(help+i); P1 = (P*R1)%MOD; R1*=47;R1%= MOD; NASH1 = (NASH1+P1)%MOD; } } //printf("%d %lld %lld %lld %lld %lld %lld\n",node,NASH1,HASH1,SeqAt(help),SignalAt(1),SeqAt(help+M-1),SignalAt(M)); if(SeqAt(help)==SignalAt(1) && SeqAt(help+M-1)==SignalAt(M)){ if(CompHashes(NASH1,0,HASH1,0,47)){ ++wynik; //printf("START %lld %d\n",help,node); } } G1 = G2 = 1; for(LL i=help+1;i<=endP;++i){ AA = i+M-1; if(AA>N)break; P = SeqAt(i-1); NASH1-= P*G1; NASH1 = MD(NASH1); P = SeqAt(AA); NASH1 = (NASH1+P*R1)%MOD; G1*=47;G1%= MOD; R1*=47;R1%= MOD; if(SeqAt(i)==SignalAt(1) && P==SignalAt(M)){ if(CompHashes(NASH1,i-help,HASH1,0,47)){ //printf("START %lld %d\n",i,node); ++wynik; } } } //printf("%d %lld\n",node,wynik); PutLL(0,wynik); Send(0); } else{ HASH1 = 0;HASH2 = 0; for(int i=1;i<=cNodes;++i){ Receive(i); help = podzial*(i-1); G1 = GetLL(i); HASH1+= G1*PTT(47,help); HASH1%= MOD; } for(int i=1;i<=cNodes;++i){ PutLL(i,HASH1); Send(i); } for(int i=1;i<=cNodes;++i){ Receive(i); wynik+= GetLL(i); } printf("%lld\n",wynik); } return 0; } LL PTT(LL x,LL y){ LL W = 1; int pt = 1; while(pt<=y){ if(pt&y){ W*=x; W%=MOD; } pt*=2; x*=x; x%=MOD; } return W; } bool CompHashes(LL H1,LL S1,LL H2, LL S2,LL P){ if(S1>S2){ H2*=PTT(P,S1-S2); H2%= MOD; } else if(S1<S2){ H1*=PTT(P,S2-S1); H1%= MOD; } return H1==H2; } void PrintHashes(LL H1,LL S1,LL H2, LL S2,LL P){ if(S1>S2){ H2*=PTT(P,S1-S2); H2%= MOD; } else if(S1<S2){ H1*=PTT(P,S2-S1); H1%= MOD; } printf("%lld %lld\n",H1,H2); } |