Haymouth the cow is playing with a toy today. Unfortunately, the toy's inner workings are a little too complicated for his bovine brain.
Engel's Enigma is a circle puzzle consisting of 21 pieces laid out in two interlocking circles. The circles, one on the left and one on the right, can each be turned 60-degrees in either direction. After a 60-degree turn, the pieces line up such that both circles are free to turn again. However, during each 60-degree turn, the other pieces in the other circle are locked in place and cannot move.
For example, suppose that the toy's initial state is as follows, with each piece labeled differently except for the colourless pieces to which we label '-':
C J
B - - K
A D L
- E -
I F M
H - - N
G O
Turning the right circle clockwise results in the following state:
C D
B - E -
A F J
- - K
I O L
H - N -
G M
Following that, turning the left circle clockwise, and then the right circle anti-clockwise again results in:
A J
- B - K
I D L
H E -
G C M
- - - N
O F
The goal of the game is to reassemble the neatly ordered state from a jumbled state. However, that task is too complex for Haymouth. In fact, he is failing even to understand how the moves actually work. For example, he does not see why the final state will be as follows if we had not turned the right circle clockwise in the beginning but still turned the left circle clockwise and then the right circle anti-clockwise:
A L
- B K -
I J M
H - N
G C O
- E - -
F D
Haymouth would like to actually understand how Engel's Enigma works. He'd like to make a few moves and immediately know what the result will be at any point along the set of moves. He'd also like to be able to amend his list of moves by adding or deleting moves. Write a program to help Haymouth visualize the moves.
Implementation
You are to submit one file containing implementation for four functions. Include the header file engel.h at the beginning of your program.
-
void init(char state[21])
This function will be called once, before all the other calls.
char state[21]: This is a character array containing the initial state of the toy. Each character represents a piece. The pieces are ordered in a left-to-right fashion, row by row. The initial state as shown above, which is the same for all test cases, will be represented in the array as "CJB--KADL-E-IFMH--NGO". Initially, Haymouth's list of moves is empty. Moves will only be added or removed by calling add_move or cancel_move.
-
void add_move(int K, char move)
This function will be called whenever Haymouth wants to add a move to his list of moves.
int K: This integer represents where Haymouth wants to insert the new move. Numbering the moves from 0, K is what the number of the new move should be. Let the the previous number of moves in the list be S. 0 ≤ K ≤ S holds for all calls made to add_move.char move: This character represents the move Haymouth wants to insert. 'L' and 'R' (in uppercase) represent rotating the left and right circle clockwise respectively. Similarly, 'l' and 'r' (in lowercase) represent rotation the left and right circle anti-clockwise respectively.
-
void cancel_move(int K)
This function will be called whenever Haymouth wants to cancel a move from his list of moves.
int K: This integer represents the number of the move Haymouth wants to cancel, numbering the moves from 0. Let the previous number of moves in the list be S. 0 ≤ K < S hold for all calls made to cancel_move.
-
void query_state(int K, char output_state[21])
This function will be called whenever Haymouth wants to know the state of the Engel's Enigma after a number of moves.
int K: Haymouth wants to know the state of the Engel's Enigma after K moves from the beginning. Let the previous number of moves in the list be S. 0 ≤ K ≤ S hold for all calls made to query_state.char output_state[21]: This is an output parameter. After query_state returns, output_state should contain the state of the Engel's Enigma after K moves, stored in the same format as the one the initial state is given in.
Subtasks
Let Q be the total number of calls to add_move, cancel_move and query_state.
-
Subtask 1 (15 points): 1 ≤ Q ≤ 5 000.
-
Subtask 2 (17 points): 1 ≤ Q ≤ 200 000. In addition, all calls to add_move, cancel_move and query_state will satisfy the following constraints, where S denotes the number of moves in Haymouth's list of moves before the function is called:
add_move: K = S.cancel_move: K = S - 1.query_state: K = S.
-
Subtask 3 (68 points): 1 ≤ Q ≤ 200 000.
Grader
A sample grader is provided for your convenience. It also contains a function to print the state in a human-readable way, which you may or may not find useful during the course of your implementation.
Grader Input
The sample grader reads input in the format described below.
- On the first line, there is one integer Q. This is the number of operations Haymouth will perform on his list of moves.
- The next 7 lines are the same for every test case. They contain the initial state of the toy.
- The next Q lines contain one operation each. Every operation begins with an uppercase character T.
- If T is
'A', the operation is the add_move operation. One integer K and one non-whitespace character move follow, representing the parameters that will be supplied to add_move.
- If T is
'C', the operation is the cancel_move operation. One integer K will follow, representing the parameter K that will be supplied to cancel_move.
- If T is
'Q', the operation is the query_state operation. One integer K will follow, representing the parameter K that will be supplied to cancel_move.
Grader Output
The sample grader outputs in the format described below:
- For every
query_state operation, one line will be printed, containing the 21 characters in the output_state array after query_state is called on it.
Sample Grader Input
9
C J
B - - K
A D L
- E -
I F M
H - - N
G O
A 0 R
A 1 r
A 1 L
Q 0
Q 1
Q 2
Q 3
C 0
Q 2
Sample Grader Output
CJB--KADL-E-IFMH--NGO
CDB-E-AFJ--KIOLH-N-GM
AD-BE-ICJH-KGFL--N-OM
AJ-B-KIDLHE-GCM---NOF
AL-BK-IJMH-NGCO-E--FD
Explanation
This is the same situation as the one described above.