Codeforces 222 B. Cosmic Tables

Codeforces

問題

n行m列の行列が与えられる。
この行列に対して次のようなクエリがk個与えられるので、処理せよ。

  • g x y : x行y列の値を出力する
  • c x y : x列とy列を入れ替える
  • r x y : x行とy行を入れ替える

制約条件

n, m≦1000
k≦5*10^5

方針

愚直に入れ替えるとTLE.


行の入れ替えと、列の入れ替えは順序を入れ替えても結果は変わらない。
なので、現在どの行とどの行が入れ替わっているか、
どの列とどの列が入れ替わっているかだけを覚えておけば、入れ替えがO(1)で出来る。

ソースコード

int h, w, q, a[1000][1000];
int r[1000], c[1000];

int main(){
	scanf("%d%d%d", &h, &w, &q);
	rep(i, h) rep(j, w) scanf("%d", a[i] + j);
	rep(i, h) r[i] = i;
	rep(i, w) c[i] = i;
	
	rep(i, q){
		char t;
		int x, y;
		scanf(" %c%d%d", &t, &x, &y);
		x--; y--;
		if(t == 'g') printf("%d\n", a[r[x]][c[y]]);
		else if(t == 'r') swap(r[x], r[y]);
		else swap(c[x], c[y]);
	}
	
	return 0;
}