Codeforces #641 Div1 C. Orac and Game of Life

なんだこのメモリ制限。
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にしては簡単。