median
これも相当厄介(めんどくささが)。配列がランダムなことからハッシュが有効だというのがわかる。さらに、この問題ではかつてのプラクティスにあったshhhで使ったテクがかなり有効利用できる。
しかしいかんせん実装量が多くて複雑でテストが微妙なので、例によって通るかどうかヒヤヒヤな問題...。なんか一箇所変えたらACになったが。変えた場所がどういう意味を持ってるのかはわからん。
変なマジックナンバーを持ち出したいときはちゃんと素数をもってきましょう。
long long D=1000000000000000LL; pair<wolf,long long> ev[1100]; int ps[1100]; wolf pk[1100]; int rn[1100000]; int vsz[1100]; int F=33000; int cnt[40000]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); if(I==T-1){ for(int i=0;i<1000000;i++){ rn[i]=GetData((long long)(xrand()%1000000000000000LL)); } std::sort(rn,rn+1000000); int Cnt=0; for(int i=0;i<1000000;i++){ if(i&&rn[i]==rn[i-1])Cnt++; else Cnt=1; if(Cnt>600000){ printf("%d\n",rn[i]); for(int i=0;i<T-1;i++){ PutInt(i,0); Send(i); } return 0; } } for(int i=0;i<T-1;i++){ PutInt(i,1); Send(i); } int NK=1000; for(int i=0;i<NK;i++){ long long st=i*1000037; wolf key=0; wolf ks=1; wolf mul=1145141919; for(int j=0;j<100;j++){ key*=mul; ks*=mul; key+=GetData(D+st+j); } ev[i]=make_pair(key,st); } std::sort(ev,ev+NK); int sz=0; for(int i=0;i<NK;i++){ if(i==0||ev[i].first!=ev[i-1].first){ pk[sz]=ev[i].first; ps[sz]=ev[i].second; sz++; } } for(int i=0;i<T-1;i++){ PutInt(i,sz); for(int j=0;j<sz;j++){ PutLL(i,pk[j]); PutLL(i,ps[j]); } Send(i); } long long tot=0; for(int i=0;i<T-1;i++){ Receive(i); for(int j=0;j<33000;j++){ int tmp=GetInt(i); cnt[j]+=tmp; tot+=tmp; } } long long now=0; int pind=0; int qind=0; for(int i=0;i<33000;i++){ now+=cnt[i]; if(now*2>tot){ pind=i; now-=cnt[i]; break; } } for(int i=0;i<T-1;i++){ PutInt(i,pind); Send(i); } //tot=0; for(int i=0;i<33000;i++)cnt[i]=0; for(int i=0;i<T-1;i++){ Receive(i); for(int j=0;j<33000;j++){ int tmp=GetInt(i); cnt[j]+=tmp; //tot+=tmp; } } //now=0; for(int i=0;i<33000;i++){ now+=cnt[i]; if(now*2>tot){ qind=i;break; } } printf("%d\n",pind*33000+qind); }else{ Receive(T-1); int ch=GetInt(T-1); if(ch==0)return 0; Receive(T-1); int sz=GetInt(T-1); for(int i=0;i<sz;i++){ pk[i]=GetLL(T-1); ps[i]=GetLL(T-1); } wolf key=0; wolf ks=1; wolf mul=1145141919; for(int i=0;i<100;i++){ key*=mul; ks*=mul; key+=GetData(D+i); } long long ind=0; long long os=0; while(1){ int at=lower_bound(pk,pk+sz,key)-pk; if(pk[at]==key){ // printf("%d %lld\n",ps[at],ind); os=ps[at]-ind; break; } key*=mul; key+=GetData(D+ind+100); key-=ks*GetData(D+ind); ind++; } // printf("%lld\n",(os+11)%11); int L=sz*I/(T-1); int R=sz*(I+1)/(T-1); for(int i=L;i<R;i++){ key=0; ks=1; mul=1145141919; for(int j=0;j<100;j++){ key*=mul; ks*=mul; key+=GetData(D+ps[i]-os+j); } while(1){ key*=mul; key+=GetData(D+ps[i]-os+vsz[i]+100); int tmp=GetData(D+ps[i]-os+vsz[i]); cnt[tmp/F]++; key-=ks*tmp; vsz[i]++; if(binary_search(pk,pk+sz,key)){ break; } } } for(int i=0;i<33000;i++){ PutInt(T-1,cnt[i]); } Send(T-1); for(int i=0;i<33000;i++)cnt[i]=0; Receive(T-1); int tar=GetInt(T-1); for(int i=L;i<R;i++){ for(int j=0;j<vsz[i];j++){ int tmp=GetData(D+ps[i]-os+j); // printf("%d %lld\n",i,((ps[i]+j)%17+17)%17); if(tmp/F==tar)cnt[tmp%F]++; } } for(int i=0;i<33000;i++){ PutInt(T-1,cnt[i]); } Send(T-1); } }
