tozangezan's diary

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

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

lispp3 Small

Largeはあまりにも虚無なので無視。
Smallの重要な点は、stackの分散のうまい方法としては、余った部分と不足部分の両方をあつめてくることで、masterで過不足がうまくあっているかを判定できる。
ただしこの問題では問題依存なテクニックが多い(+が少ないときはmasterに送る長さが短くていいとか)ので、応用性に乏しい。
気をつけるべきこととしては、masterを用意する場合は全部で99スレッドになるので、配列長が10100000では足りない。10110000にすると足りる。
smallだからというのもあるが、そこまで罠が多い問題ではない。おすすめもしないけど。

int L_ind[10110000];
char L_ch[10110000];
char R_ch[10110000];
int R_ind[10110000];
int rsz[110];
int lsz[110];
int rind[110][310];
int lind[110][310];
char lst[110][310];
char rst[110][310];
int rnew[110];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetLength();
	if(I==T-1){
		int error=N;
		int perror=N;
		for(int i=0;i<T-1;i++){
			Receive(i);
			int tmp=GetInt(i);
			if(tmp!=-1)perror=min(perror,tmp);
			rnew[i]=GetInt(i);
			rsz[i]=GetInt(i);
			for(int j=0;j<rsz[i];j++){
				rind[i][rsz[i]-1-j]=GetInt(i);
				rst[i][rsz[i]-1-j]=GetCharacter(rind[i][rsz[i]-1-j]);
			}
			lsz[i]=GetInt(i);
			for(int j=0;j<lsz[i];j++){
				lind[i][j]=GetInt(i);
				lst[i][j]=GetCharacter(lind[i][j]);
			}
		}
		int R_sz=0;
		bool ed=false;
		bool R_new=true;
		int prev=-1;
		for(int i=0;i<T-1;i++){
			long long L=(long long)N*i/(T-1);
			long long R=(long long)N*(i+1)/(T-1);
			for(int j=0;j<lsz[i];j++){
				if(R_sz==0){
					error=lind[i][j];
					ed=true;break;
				}
				if(lind[i][j]>prev+1)R_new=false;
				prev=lind[i][j];
				if(lst[i][j]=='+'){
					if(!R_new&&R_ch[R_sz-1]=='('){
						R_ch[R_sz++]='+';
						R_new=true;
					}else{
						error=lind[i][j];ed=true;break;
					}
				}else{
					if((!R_new&&R_ch[R_sz-1]=='+')||(R_new&&R_ch[R_sz-1]=='(')){
						if(!R_new)R_sz-=2;
						else R_sz--;
						R_new=false;
					}else{
						error=lind[i][j];ed=true;break;
					}
				}

			}
			if(ed)break;
			for(int j=0;j<rsz[i];j++){
				if(rind[i][j]>prev+1)R_new=false;
				prev=rind[i][j];
				if(rst[i][j]=='('){
					R_ind[R_sz]=i;
					R_ch[R_sz++]=rst[i][j];
					R_new=true;
				}else if(rst[i][j]=='+'){
					if(!R_new&&R_ch[R_sz-1]=='('){
						R_ch[R_sz++]=rst[i][j];
						R_new=true;
					}
				}
			}
			if(ed)break;
		//	R_ch[R_sz]=0;printf("%d: %s\n",R_new,R_ch);
		}
		error=min(error,perror);
		if(error==N&&R_sz==0)error=-1;
		printf("%d\n",error);
	}else{
		long long L=(long long)N*I/(T-1);
		long long R=(long long)N*(I+1)/(T-1);
		int L_sz=0;
		int R_sz=0;
		bool R_new=false;
		int error=-1;
		for(int i=L;i<R;i++){
			char ch=GetCharacter(i);
			if(ch=='('){
				R_ind[R_sz]=i;
				R_ch[R_sz++]=ch;
				R_new=true;
			}else if(ch=='+'){
				if(R_sz==0){
					L_ind[L_sz]=i;
					L_ch[L_sz++]=ch;
				}else{
					if(!R_new&&R_ch[R_sz-1]=='('){
						R_ind[R_sz]=i;
						R_ch[R_sz++]=ch;
						R_new=true;
					}else{
						error=i;break;
					}
				}
			}else{
				if(R_sz==0){
					L_ind[L_sz]=i;
					L_ch[L_sz++]=ch;
				}else{
					if((!R_new&&R_ch[R_sz-1]=='+')||(R_new&&R_ch[R_sz-1]=='(')){
						if(R_ch[R_sz-1]=='+')R_sz-=2;
						else R_sz--;
						R_new=false;
					}else{
						error=i;break;
					}
				}
			}
		}
		PutInt(T-1,error);
		int se_t=0;
		if(R_new)se_t=1;
		PutInt(T-1,se_t);
		PutInt(T-1,min(210,R_sz));
		for(int i=0;i<min(210,R_sz);i++){
			PutInt(T-1,R_ind[R_sz-1-i]);
		}
		PutInt(T-1,min(210,L_sz));
		for(int i=0;i<min(210,L_sz);i++){
			PutInt(T-1,L_ind[i]);
		}
		R_ch[R_sz]=0;
		L_ch[L_sz]=0;
	//	printf("%s\n",R_ch);
	//	printf("%s\n",L_ch);
		
		Send(T-1);
	}

}