#include <iostream> #include <cassert> #include <cstdlib> #include <cstdio> using namespace std; #include "poszukiwania.h" #include "message.h" long long liczenie( int pocz, int kon ){ int x=31; long long j=1, potega=1, y=1000000007, wynik=0, hashw=0, hashwpop=0, hash[1000005], wzor=SignalLength(); hash[0]=0; for( int i=1; i<=wzor; i++ ){ potega=(potega*31)%y; } for( int i=1; i<=SignalLength(); i++ ){ hashw=(hashwpop*x+SignalAt(i))%y; hashwpop=hashw; } // printf("%lld %lld", pocz, kon); for( int i=pocz; i<=kon; i++ ){ hash[j]=(hash[j-1]*x+SeqAt(i))%y; if( i-wzor+1>=pocz ){ if( (hash[j]-(hash[j-wzor]*potega)%y)%y==hashw ) wynik++; } j++; } for( int i=1; i<=1000001; i++ ){ hash[i]=0; } return wynik; } int main(){ if( SignalLength()>1000000 ){ if( MyNodeId()==0 ){ printf("0\n"); } return 0; } int wzor=SignalLength(); int ciag=SeqLength(); int N=NumberOfNodes(); int node=MyNodeId(); int p=0; int k=0; long long odp=0; if( node>0 ){ if( ciag/(N/2)>=wzor ){ int dlugosc=ciag/(N/2); int dlugosc_ost=ciag-(((N/2)-1)*dlugosc); if( node>=1 && node<N/2 ){ p=(node-1)*dlugosc+1; k=p+dlugosc-1; } if( node==N/2 ){ p=((N/2)-1)*dlugosc+1; k=ciag; } if( node>N/2 && node<=2*(N/2)-1 ){ p=(node-(N/2))*dlugosc+2-wzor; k=(node-(N/2))*dlugosc+wzor-1; } } else{ int dlugosc=wzor; int glowne=(ciag+(wzor-1))/wzor; int graniczne=glowne-1; if( node<glowne ){ p=((node-1)*dlugosc)+1; k=p+dlugosc-1; } if( node==glowne ){ p=((node-1)*dlugosc)+1; k=ciag; } if( node>glowne && node<=glowne+graniczne ){ p=((node-glowne)*wzor)+2-wzor; k=min(ciag, (((node-glowne)*wzor)+wzor-1)); } } if( p<k && k-p<=1000000 ) odp=liczenie(p, k); PutLL(0, odp); Send(0); } if( node==0 ){ long long sum=0; for( int i=1; i<N; i++ ){ Receive(i); long long wartosc=GetLL(i); sum+=wartosc; } printf("%lld\n", sum); } 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 | #include <iostream> #include <cassert> #include <cstdlib> #include <cstdio> using namespace std; #include "poszukiwania.h" #include "message.h" long long liczenie( int pocz, int kon ){ int x=31; long long j=1, potega=1, y=1000000007, wynik=0, hashw=0, hashwpop=0, hash[1000005], wzor=SignalLength(); hash[0]=0; for( int i=1; i<=wzor; i++ ){ potega=(potega*31)%y; } for( int i=1; i<=SignalLength(); i++ ){ hashw=(hashwpop*x+SignalAt(i))%y; hashwpop=hashw; } // printf("%lld %lld", pocz, kon); for( int i=pocz; i<=kon; i++ ){ hash[j]=(hash[j-1]*x+SeqAt(i))%y; if( i-wzor+1>=pocz ){ if( (hash[j]-(hash[j-wzor]*potega)%y)%y==hashw ) wynik++; } j++; } for( int i=1; i<=1000001; i++ ){ hash[i]=0; } return wynik; } int main(){ if( SignalLength()>1000000 ){ if( MyNodeId()==0 ){ printf("0\n"); } return 0; } int wzor=SignalLength(); int ciag=SeqLength(); int N=NumberOfNodes(); int node=MyNodeId(); int p=0; int k=0; long long odp=0; if( node>0 ){ if( ciag/(N/2)>=wzor ){ int dlugosc=ciag/(N/2); int dlugosc_ost=ciag-(((N/2)-1)*dlugosc); if( node>=1 && node<N/2 ){ p=(node-1)*dlugosc+1; k=p+dlugosc-1; } if( node==N/2 ){ p=((N/2)-1)*dlugosc+1; k=ciag; } if( node>N/2 && node<=2*(N/2)-1 ){ p=(node-(N/2))*dlugosc+2-wzor; k=(node-(N/2))*dlugosc+wzor-1; } } else{ int dlugosc=wzor; int glowne=(ciag+(wzor-1))/wzor; int graniczne=glowne-1; if( node<glowne ){ p=((node-1)*dlugosc)+1; k=p+dlugosc-1; } if( node==glowne ){ p=((node-1)*dlugosc)+1; k=ciag; } if( node>glowne && node<=glowne+graniczne ){ p=((node-glowne)*wzor)+2-wzor; k=min(ciag, (((node-glowne)*wzor)+wzor-1)); } } if( p<k && k-p<=1000000 ) odp=liczenie(p, k); PutLL(0, odp); Send(0); } if( node==0 ){ long long sum=0; for( int i=1; i<N; i++ ){ Receive(i); long long wartosc=GetLL(i); sum+=wartosc; } printf("%lld\n", sum); } return 0; } |