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

broken_memory

二分探索で変なところは探せる。3個以上のノードのデータをまとめれば、全ての答えがわかる。
hashingが難しい。2個の間違ったデータを含むときと1個も含まないときでハッシュ値がちゃんと異なるように設定しよう。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include<set>
#include"broken_memory.h"
using namespace std;

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB
Send, Receive / 5 ~ 10ms?
Linear Message passing: slow (500ms through every nodes)

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
long long in[10100000];
long long xs[10100000];
int fn[1100][2];
int pp[1100];
int ans[1100];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetLength();
	for(int i=0;i<N;i++){
		in[i]=GetValue(i);
		in[i]*=(i*i*9+i*13+14);
		in[i]+=(in[i]<<11)+(in[i]<<22)+(in[i]>>15);
		xs[i+1]=xs[i]^in[i];
	}
	if(I%5==0){
		for(int ii=1;ii<5;ii++){
			int i=I+ii;
			int left=-1;
			int right=N;
			long long tmp=0;
			while(left+1<right){
				int M=(left+right)/2;
				PutInt(i,M);
				Send(i);
				Receive(i);
				long long ff=GetLL(i);
				if(ff!=xs[M+1]){
					right=M;
					tmp=ff;
				}else{
					left=M;
				}
			}
			fn[i][0]=right;
			left=right;
			right=N;
			while(left+1<right){
				int M=(left+right)/2;
				PutInt(i,M);
				Send(i);
				Receive(i);
				long long ff=GetLL(i)^tmp;
				if(ff!=(xs[M+1]^xs[fn[i][0]+1])){
					right=M;
				}else{
					left=M;
				}
			}
			fn[i][1]=right;
			PutInt(i,1145141919);
			Send(i);
		}

		int sz=0;
		for(int ii=1;ii<5;ii++){
			int i=I+ii;
			for(int j=0;j<2;j++){
				pp[sz++]=fn[i][j];
			}
		}
		std::sort(pp,pp+sz);
		for(int i=1;i<sz;i++){
			if(pp[i]==pp[i-1]){
				ans[I]=pp[i];break;
			}
		}
		for(int ii=1;ii<5;ii++){
			int i=I+ii;
			for(int j=0;j<2;j++){
				if(fn[i][j]!=ans[I]){
					ans[i]=fn[i][j];
				}
			}
		}
		if(I==0){
			for(int i=5;i<T;i+=5){
				Receive(i);
				for(int j=0;j<5;j++){
					ans[i+j]=GetInt(i);
				}
			}
			for(int i=0;i<T;i++){
				if(i)printf(" ");
				printf("%d",ans[i]);
			}
			printf("\n");
		}else{
			for(int i=0;i<5;i++){
				PutInt(0,ans[I+i]);
			}
			Send(0);
		}

	}else{
		while(1){
			Receive(I-I%5);
			int at=GetInt(I-I%5);
			if(at==1145141919){
				break;
			}else{
				PutLL(I-I%5,xs[at+1]);
				Send(I-I%5);
			}
		}
	}
}