トロントに行きたいけど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); } }