tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

トロントに行きたいけどGCJは無理そうだからDCJの対策をする狼。三日目。

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);
	}
}