ACS - A concrete simulation

You are given a matrix M of type 1234x5678. It is initially filled with integers 1...1234x5678 in row major order. Your task is to process a list of commands manipulating M. There are 4 types of commands:

  • "R x y" swap the x-th and y-th row of M;
  • "C x y" swap the x-th and y-th column of M;
  • "Q x y" write out M(x,y);
  • "W z" write out x and y where z=M(x,y).

Input

A list of valid commands. Input terminated by EOF.

Output

For each "Q x y" write out one line with the current value of M(x,y), for each "W z" write out one line with the value of x and y (interpreted as above) separated by a space.

Input:
R 1 2
Q 1 1
Q 2 1
W 1
W 5679
C 1 2
Q 1 1
Q 2 1
W 1
W 5679

Output:
5679
1
2 1
1 1
5680
2
2 2
1 2

Added by:czylabsonasa
Date:2005-06-10
Time limit:7s
Source limit:7777B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Folklore

hide comments
2015-06-21 20:30:48
Getting WA :(
Any corner cases ? :/
2015-06-01 08:32:54 aksam
my 100 classical problem :D
2015-04-01 21:57:34 Rajat (1307086)
Try O(1) for all queries. AC in .05
2015-02-09 21:09:34 achint mittal
please can anyone give more testcases..
2015-01-01 20:03:41 Malinga
easy problem..got ac in 0.01 sec ..O(1) for all the queries..I used two 1236 length arrays and two 5678 length arrays..
2014-12-19 20:02:18 Rahul Jain
guys, please tell me some tricky cases
<snip>

Last edit: 2022-09-13 17:33:04
2014-12-19 19:04:15 Harsh Rumalwala
Done without pre-computation.Need to think a bit!!!Corner cases gave me a WA.
2014-09-03 10:49:11 Shaktiman
Q- O(1)
W- O(row+column)
2014-06-22 13:45:23 Divyank Duvedi
What is Matrix's initial form is it :- a[r][c]=r*c ?
2014-04-19 19:37:37 Rishab Banerjee
O(1) per query is not required....my solution took O(1) in R and C
linear time in W and Q
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.