Description

Modified from 10389 - text editor

In this problem we simulate a simple text editor. Given a series of keyboard input, output the final text content. Initially, the text content is empty and the cursor is at the beginning of the line. The user can:

1. Insert a lower-case alphabet ('a-z') before the cursor, denoted as a lower-case alphabet.

2. Erase an alphabet before the cursor, denoted as B.

3. Move the cursor to the right one character at a time, denoted as R.

4. Move the cursor to the left one word at a time, denoted as L.

Hints

In this problem, you are asked to use doubly linked list to reduce the time complexity. Three typical implementations as follows are possible. You can choose your favorite one, e.g., Impl 1 or Impl 2.

Remember to free memory when a linked list node is deleted. If you get Runtime Error on test case, probably there is something wrong with the pointers or there is memory leak in your program.

Make sure the time complexity is O(1) for each operation, otherwise you may get Time limit exceed

Input

The first line is an integer T (1 <= T <= 50), meaning that there are T subtasks in the input.

In each subtask, there are two lines. The first line is an integer N(1<= N <= 10⁶), being the length of the series of keyboard input. The next line is a string of length N, being the series of keyboard input.

It is guaranteed that L and B will not occur when the cursor is in the left-most position, R will not occur when the cursor is in the right-most position.

Output

For each subtask, output the final text content in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. Lu is a famous magician. There’s a poker magic tutorial on his youtube channel.
There’re N stacks of cards on the table at begining.
And then, Mr. Lu make M actions on these card stacks.
There’s only two kinds of actions Merge and Cut:

• Merge x y: put the x-th card stack on the top of y-th card stack.
• Cut x i: cut the x-th card stack into two stacks. One is the card stack contains ( 1~i )-th cards of original stack. The other one is the remaining. The former’s index will be x, the latter’s will be (x+1)
• The indexes of stacks and cards will be changed after Merge and Cut.

For example:

As a lazy CS student, you only focus on the result.
Therefore, you decide to write a program to compute the final state of card stacks.

It’s partial judge for this problem.
Please download the code at the bottom to see the interface and main function.
You have to implement a data structure like below:

Input

Two integer N,M on the first line.
For each of the next N lines, there’re several integers Ni and Ci,1,Ci,2...Ci,Ni.
Ni means the number of cards in the i-th stack.
Ci,j denotes the j-th card of i-th stack.

The folloing M lines contains one action per line.
Every Action is one of “Merge x y” or “Cut x i”.

It’s guaranteed that:

• 1 ≤ N, M ≤ 9000
• ∑ Ni ≤ 4∗10⁴
• Ci,j is non-negative integer.
• In “Merge x y” action:
  • the x, y-th stacks always exist.
  • x is not equal to y.
• In “Cut x i” action:
  • the x-th stack always exists.
  • i is always between 1 and Nx - 1.
• There’s at least 1 card in each card stack.

Output

Print the card stacks by the order of index.
One line for one card stack.

Please refer to the sample input/output for the precise format.
There is a ‘\n’ at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12680.c

Partial Judge Header

12680.h

Tags

Discuss

Description

This is a partial judge problem OwO

Finally, Spongebob and Patrick have successfully escaped from the police capture. So it’s unnecessary for Patrick to cosplay as a ninja, aka Patruto. (To know what happened before, you can refer to 12884 - Patruto and Spongebob run away.)

In order to enjoy their life of leisure, they decided to go catch some jellyfish for fun. But due to their poor reading ability, they eventually go to the "JerryFish" Field.

After arriving the JerryFish Field, they observed that some JerryFish would form a circle. And they always move regularly: two groups of consecutive JerryFish would exchange their position without messing up the order inside a group.

Now you need to help Spongebob and Patrick record the information of JerryFish circle. Formally there are N JerryFish. For convenience, we always number all the JerryFish from 1 to N in clockwise order. In the beginning, we know the beautiful value of the i-th JerryFish is v_i.
Then there are Q events. In the i-th event, two groups of consecutive JerryFish would exchange their position. And the number of JerryFish of these two groups is len_i. One group is the len_i consecutive JerryFish which start from the a_i-th JerryFish(in clockwise order). Another group is the len_i consecutive JerryFish which start from the b_i-th JerryFish(in clockwise order). They will exchange their position simultaneously. Note we always number all the JerryFish from 1 to N in clockwise order. So after one event, you may need to re-number all the JerryFish.

In the end, tell Spongebob and Patrick the beautiful value of all the JerryFish (in clockwise order).

Sample Explanation

Let's take Sample as an example. In Sample, N = 6 and Q = 3.

The first event: the 2nd JerryFish exchange its postion with the 4th JerryFish.

 

The second event: the 1st and the 2nd JerryFish exchange their postion with the 5th and the 6th JerryFish.

The third event: the 6th and the 1st JerryFish exchange their postion with the 3rd and the 4th JerryFish.

Finally the beautiful value of all the JerryFish are: 2 6 4 5 1 3.

Partial Code

Let's solve this problem with a circular linked list.

main.c

#include <stdio.h>
#include "function.h"
#define MAXN 100005
int arr[MAXN];
int main() {
    int N;
    scanf("%d", &N);
    for(int i=1;i<=N;i++)
        scanf("%d", &arr[i]);

    Node *head = NULL;
    createLinkedList(&head, N, arr);

    int Q;
    scanf("%d", &Q);
    for(int i=1;i<=Q;i++) {
        int a,b,len;
        scanf("%d %d %d", &a, &b, &len);
        swapTwoSegment(&head, a, b, len);
    }

    for(int i=1;i<=N;i++) {
        if(i > 1)    printf(" ");
        printf("%d", head->val);
        head = head->next;
    }
    printf("\n");
    return 0;
}

function.h

typedef struct node {
    struct node* next;
    int val;
} Node;
void createLinkedList(Node **head, int N, int *arr);
void swapTwoSegment(Node **head, int a, int b, int len);

You need to implement the two functions: createLinkedList and swapTwoSegment.

Input

The first line contains one integer N (2 ≤ N ≤ 10⁵) – the number of JerryFish.

The second line contains N integers v₁, v₂, ..., v_N (1 ≤ v_i ≤ N) – the beautiful value of each JerryFish.

The third line contains one integer Q (1 ≤ Q ≤ 100) – the number of events.

Then Q lines follow. The i+3-th line contains three integer a_i, b_i and len_i (1 ≤ a_i, b_i ≤ N, 1 ≤ 2 x len_i ≤ N) – the number of the starting JerryFish of two groups and the number of JerryFish in these two groups. It's guaranteed that there must not be such a JerryFish which is in the two groups simultaneously in each event.

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample below

Output

After all the events output the beautiful value of all the JerryFish(in clockwise order).

Sample Input  Download

Sample Output  Download

Partial Judge Code

13133.c

Partial Judge Header

13133.h

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 sz_i people. Note row may be empty(i.e. sz_i = 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 c_ij.

Squidward ask them to move Q times. In each move, there are three types of moving:

1. all the people in the a_i-th row move to the front of the b_i-th row (without messing up the original order)
2. all the people in the a_i-th row move to the back of the b_i-th row (without messing up the original order)
3. exchange all the people in the a_i-th row and the b_i-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 ≤ 10⁵) – the number of rows.

Then N lines follow. First the i+1-th line contains one integer sz_i – the number of people in the i-th row. If there are some people in the row, a space character and sz_i characters c_ij are followed where c_ij is the musical instrument played by the j-th people in the i-th row. The sum of all the sz_i is less than or equal to 10⁶.

The N+2-th line contains one integer Q (1 ≤ Q ≤ 10⁵) – the times they need to move.

Then Q lines follow. The i+N+3-th line contains three integer type_i, a_i, b_i (1 ≤ type_i ≤ 3, 1 ≤ a_i, b_i ≤ N, a_i ≠ b_i) – 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 ≤ 10³, the sum of all the sz_i ≤ 10⁴

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.

Sample Input  Download

Sample Output  Download

Tags

Discuss