なんだこのメモリ制限。
http://codeforces.com/contest/1349/problem/C
問題
H*Wのグリッドがあり、各セルは白黒いずれかで塗られており、時刻0の時の色が与えられる。
時刻tに各セルにおいて隣接セルのうち1個でも同色のセルがあるとき、時刻t+1にはそのセルの色が反転する。
Q個のクエリが与えられる。
各クエリではセルの位置と時刻が与えられるので、そのセルの色を答えよ。
解法
一端色が変わり始めたセルは、以後毎時色が反転する。
また、それまで色が変わっていなくても、隣接セルが色を変え始めると、次の時刻から色が反転する。
そこで、BFSで各セル色が反転し始める時刻を求めておけば、前処理でO(HW)、各クエリはO(1)で回答できる。
int H,W,T; vector<bitset<1024>> B; string S[1010]; int Y,X; ll P; ll step[1010][1010]; /* vector<bitset<1024>> step(vector<bitset<1024>> S) { vector<bitset<1024>> R=S; int y,x; FOR(y,H) FOR(x,W) { int is=0; if(y&&S[y-1][x]==S[y][x]) is++; if(y+1<H&&S[y+1][x]==S[y][x]) is++; if(x&&S[y][x-1]==S[y][x]) is++; if(x+1<W&&S[y][x+1]==S[y][x]) is++; if(is) R[y][x]=R[y][x]^1; } return R; } */ void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>T; B.resize(H); FOR(y,H) { cin>>s; FOR(x,W) { if(s[x]=='1') B[y][x]=1; step[y][x]=1LL<<60; } } queue<int> Q; FOR(y,H) FOR(x,W) { int is=0; if(y&&B[y-1][x]==B[y][x]) is++; if(y+1<H&&B[y+1][x]==B[y][x]) is++; if(x&&B[y][x-1]==B[y][x]) is++; if(x+1<W&&B[y][x+1]==B[y][x]) is++; if(is) step[y][x]=0, Q.push(y*1000+x); } while(Q.size()) { y=Q.front()/1000; x=Q.front()%1000; Q.pop(); FOR(i,4) { int dd[4]={1,0,-1,0}; int ty=y+dd[i]; int tx=x+dd[i^1]; if(ty<0 || ty>=H || tx<0 || tx>=W) continue; if(step[ty][tx]<=step[y][x]+1) continue; step[ty][tx]=step[y][x]+1; Q.push(ty*1000+tx); } } FOR(i,T) { cin>>Y>>X>>P; Y--; X--; if(P<=step[Y][X]) { cout<<B[Y][X]<<endl; } else { cout<<(B[Y][X]^((P-step[Y][X])%2))<<endl; } } /* FOR(i,10) { cout<<i<<endl; FOR(y,H) { FOR(x,W) cout<<B[y][x]; cout<<endl; } B=step(B); } */ }
まとめ
Cにしては簡単。