読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #367 Div2 E. Working routine

Codeforces

これは問題設定から気づくべきだったか…。
http://codeforces.com/contest/706/problem/E

問題

N*Mの整数行列が与えられる。
ここに対し、2つの矩形範囲の内容をスワップするクエリがQ個与えられる。
(ただし、2つの範囲は共通部分を持たない他、隣接もしないことが保証されている)

クエリ完了後の行列を答えよ。

解法

愚直に行うとO(NMQ)なので当然TLEする。
ここでは2つの範囲が隣接しない点を利用しよう。

2つの矩形をスワップというが、矩形内の隣接要素同士の関係は境界以外では変化しない。
そこで境界周辺だけ処理することを考えよう。

行列について上下方向及び左右方向をそれぞれ双方向リンクリストでつないでおく。
すると各クエリに対し境界部分だけリンクリストのつなぎ替えを行えば、スワップが完了する。
こうするとO((N+M)Q)で間にあう。

int H,W,Q;
int A,B,C,D,h,w;
struct node { int v; node *L,*R,*U,*D;};
node V[1010][1010];

node* walk(int y,int x) {
	node* n=&V[0][0];
	while(y--) n=n->D;
	while(x--) n=n->R;
	return n;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	scanf("%d%d%d",&H,&W,&Q);
	FOR(y,H) FOR(x,W) scanf("%d",&V[y+1][x+1].v);
	FOR(y,H+2) FOR(x,W+2) {
		if(x<W+1) V[y][x].R=&V[y][x+1];
		if(x>0) V[y][x].L=&V[y][x-1];
		if(y<H+1) V[y][x].D=&V[y+1][x];
		if(y>0) V[y][x].U=&V[y-1][x];
	}
	
	while(Q--) {
		scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&h,&w);
		
		node *n1 = walk(A,B);
		node *n2 = walk(C,D);
		FOR(i,w) {
			swap(n1->U,n2->U);
			n1->U->D=n1;
			n2->U->D=n2;
			n1=n1->R;
			n2=n2->R;
		}
		n1=n1->L;
		n2=n2->L;
		FOR(i,h) {
			swap(n1->R,n2->R);
			n1->R->L=n1;
			n2->R->L=n2;
			n1=n1->D;
			n2=n2->D;
		}
		n1=n1->U;
		n2=n2->U;
		FOR(i,w) {
			swap(n1->D,n2->D);
			n1->D->U=n1;
			n2->D->U=n2;
			n1=n1->L;
			n2=n2->L;
		}
		n1=n1->R;
		n2=n2->R;
		FOR(i,h) {
			swap(n1->L,n2->L);
			n1->L->R=n1;
			n2->L->R=n2;
			n1=n1->U;
			n2=n2->U;
		}
	}
	
	FOR(y,H) {
		node *n = walk(y+1,1);
		FOR(x,W) _P("%d%c",n->v,(x==W-1)?'\n':' '), n=n->R;
	}
}

まとめ

隣接しない、という条件から隣接セル同士をガチャガチャいじるという発想に至るべきであった。

広告を非表示にする