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
2014-04-14 11:40:12 Bumbler
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
2014-02-11 17:13:58 Anurag yadav
try this
W 5678
ans is 1 5678
2014-01-23 20:24:10 shashank
Finally done .. after 4 WA's ..
Awesome question ...
No datastruture .. just try to find the logic .. O(1) for any query
2014-01-20 09:49:44 BLANKRK
NICE!!!
2013-12-20 19:30:10 cegprakash
Nice problem!
2011-09-20 22:35:35 BACK
is no of test case is greater than 1000000.

>>> no.

Last edit: 2011-09-21 21:32:52
2011-09-20 22:35:35 BACK
my soln is correct but i m getting wa....help someone...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.