# | Problem | Pass Rate (passed user / total user) |
---|---|---|
14220 | Do you wanna play a game ? (version 2) |
|
14226 | Band Ya Rou Ze (revisited) |
|
Description
TA Penguin07 wants to play a game with N people. Initially, these N people are lined up and numbered from 1 to N.
TA Penguin07 will issue K commands, commands i is represented as a pair of integers (Ti, Ai, Bi), and is the following operation:
- If Ti = 1, the person with number Ai have to kill min(C, Bi) people behind them. Here, C represents the number of people remaining behind them at the moment of the command.
- If Ti = 2, the person with number Ai have to kill min(C, Bi) people in front of them. In this case, C represents the number of people remaining in front of them at the moment of the command.
However, Penguin07 has poor eyesight and cannot clearly see who has been killed from the long line. So, after each command issued by Penguin07, you need to tell Penguin07 who was killed.
If the command is invalid (that person has already been killed or there is no one been killed), you should output "Penguin07 QQ" (with no quotes).
Input
The first line contains two positive integers, N and K.
The following K lines, each line represents a command in the format of three integers: (Ti, Ai, Bi).
Constraints
- Testcases 1 ~ 4: Ti = 1, Bi = 1
- Testcases 5 ~ 6: satisfy no additional constraints.
- For all test cases: 1 ≤ N, K ≤ 2 * 106, 1 ≤ Ti ≤ 2, 1 ≤ Bi ≤ 109, 1 ≤ Ai ≤ N
Output
Remember to print a ‘\n’ at the end of the output.
Do not include any spaces at the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After catching Jerryfish, Spongebob and Patrick thought they were happy enough so they went home. And then they found that Squidward had come home already :)
Squidward told them he need to drum up a marching band fast(for some reason). So he needed their help. Hence Spongebob and Patrick joined Squidward's band.
Today is their practicing day. Squidward is teaching all the members how to move at a performance. At a performance there are N rows. And in the i-th row, there are szi people. Note row may be empty(i.e. szi = 0). Everyone plays exactly one musical instrument. The musical instrument played by the j-th people in the i-th row is represented by a lower case letter cij.
Squidward ask them to move Q times. In each move, there are three types of moving:
- all the people in the ai-th row move to the front of the bi-th row (without messing up the original order)
- all the people in the ai-th row move to the back of the bi-th row (without messing up the original order)
- exchange all the people in the ai-th row and the bi-th row (without messing up the original order)
Now it’s your turn! You need to help them to move and tell Squidward the final formation in the end.
Input
The first line contains one integer N (1 ≤ N ≤ 105) – the number of rows.
Then N lines follow. First the i+1-th line contains one integer szi – the number of people in the i-th row. If there are some people in the row, a space character and szi characters cij are followed where cij is the musical instrument played by the j-th people in the i-th row. The sum of all the szi is less than or equal to 106.
The N+2-th line contains one integer Q (1 ≤ Q ≤ 105) – the times they need to move.
Then Q lines follow. The i+N+3-th line contains three integer typei, ai, bi (1 ≤ typei ≤ 3, 1 ≤ ai, bi ≤ N, ai ≠ bi) – the type of moving and the numbers of two rows which need to move.
It's guaranteed that:
- The 1st testcase must be identical to the Sample below
- For the first five testcases: 1 ≤ N, Q ≤ 103, the sum of all the szi ≤ 104
Hint:
If you have no idea how to implement, please take it as your reference.
#include <stdlib.h> #include <stdio.h> typedef struct _Node { char val; struct _Node* next; } Node; //list[i]'s head node Node *head[100005] = {}; //list[i]'s tail node Node *tail[100005] = {}; void swap(int a, int b) { //swap list[a] and list[b] Node *tmp = (Node *)malloc(sizeof(Node)); /* swap(head_node) tmp = head[a]; head[a] = head[b]; head[b] = tmp; */ /* swap(tail_node) */ } void append(int a, int b) { //append list[a] to list[b]'s behind if(head[a] == NULL) return; if(head[b] == NULL) { swap(a, b); return; } /* tail[b]->next = head[a]; tail[b] = ... ... */ }
Output
After all the moving, for each row output all the musical instrument played in that row and then print a newline('\n') character.
If there is no people in some row, just output an empty line.