ACS - A concrete simulation

no tags 

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

hide comments
aksam: 2015-06-01 08:32:54

my 100 classical problem :D

Rajat (1307086): 2015-04-01 21:57:34

Try O(1) for all queries. AC in .05

achint mittal: 2015-02-09 21:09:34

please can anyone give more testcases..

Malinga: 2015-01-01 20:03:41

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..

Rahul Jain: 2014-12-19 20:02:18

guys, please tell me some tricky cases

http://ideone.com/FznleM

Last edit: 2014-12-20 13:28:29
Harsh Rumalwala: 2014-12-19 19:04:15

Done without pre-computation.Need to think a bit!!!Corner cases gave me a WA.

Shaktiman: 2014-09-03 10:49:11

Q- O(1)
W- O(row+column)

Divyank Duvedi: 2014-06-22 13:45:23

What is Matrix's initial form is it :- a[r][c]=r*c ?

Rishab Banerjee: 2014-04-19 19:37:37

O(1) per query is not required....my solution took O(1) in R and C
linear time in W and Q

Bumbler: 2014-04-14 11:40:12

TLE with FAST I/O. and works fine without it . Please lemme know the reason behind this .
--ans(Francky)--> Last line could not be ended by '\n', it may cause TLE.
I was using getchar() unnecessarily which resulted in TLE.My O(1) solution for each query takes 1 sec. I'm precomputing the original matrix (1234*5678). How can I further reduce the time. Precomputation not required?
--No Precomputaion required. AC 0.02 sec

Last edit: 2014-04-25 13:17:32

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