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

 

At the beginning of the semester at National Pokemon University (NPU), every student is running around for the course extra selection (加簽). In the add-or-drop selection session (加退選時期), to enroll in a course, students must submit "eForms" to the teacher. Due to the limited classroom size, after the formal course selection session, the teacher would decide who is eligible to take the course from the eForm list.

Team Rocket! Prepare for trouble! And make it double!  Unfortunately, Team Rocket had hacked into the school system, and messed up the order of the eForms! The serial numbers of the eForm list are now disorderly. They are just evil! 

Help these poor pokemon restore the eForms' order - sorting them by the serial numbers!

---

This is a partial judge problem. You would only need to implement the function "eFormSort" to pass the problem. 

Each eForm contains a serial number, a student ID, and a student name. The eForm list is given as a linked list (one node for each eForm). Your task is to make the serial numbers of that linked list in ascending order by changing the order of the eForms. The given program would output the status of each eForm, which can be either "Approved" or "Pending", after you sorted the eForm list.

 

        

 

Hint. 

1. Please notice that the memory is quite limited in this problem, and you need to sort the linked list directly by updating the "next" pointers of the nodes, instead of allocating too much extra space. The given program will check if you actually perform the required node sorting.
2. There are many ways to sort the linked list, and you may refer to the following two simple approaches:

• Approach 1: Use the Bubble Sort Algorithm. In this way, we just need to implement the operation of swapping two nodes. You can refer to the following gif and pseudocode to know more about this approach.

      

         

 

• Approach 2: While traversing the linked list, if you expect a node to occur but it does not, just keep traversing backward to find the node and move it forward. You can refer to the following gif to know more about this approach.

    

Input

• The first line contains an integer N (1 ≤ N ≤ 5000) - the number of submitted eForms.
• Each of the next N lines represents an eForm:
  • Format: <serial number> <student ID> <student name> <eForm status>
  • All of the serial numbers in the eForm list are distinct integer numbers between 1 and N
  • 1 ≤ student ID ≤ 10⁹
  • 1 ≤ length of student name ≤ 1000, and the name only consists of lower-case and upper-case alphabets A-Z / a-z
  • eForm status is either "Approved" or "Pending"
• For your convenience, in the given eForm list, the serial number of the first eForm must be 1.
• For the 30% of the test cases, the serial numbers of the given eForm list would be of the form "1, N, N-1, N-2, ..., 3, 2". That is, to solve this, you can just reverse the interval of [2, N].

 

Output

If you implement the function and sort the linked list correctly, the given program would output N lines - each of the lines represents an eForm in the input's format.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

13826.c

Partial Judge Header

13826.h

Tags

Discuss

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, each time asking the person with number i to kill the person behind them.

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 behind that person), you should output "Penguin07 QQ" (with no quotes).

Input

The input start with T (1 ≤ T ≤ 5), means number of testcases.

Each testcase contains two lines.

The first line contains two integer N and K.

The second line contains K integers a₁, a₂, … , a_K,  a_i is i'th operation the person numbered a_i.

Input Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N, K ≤ 10⁶
• 1 ≤ a₁, a₂, ..., a_N ≤ N

Output

For every operation output the number of the person killed each time.

If operation is invalid, output "Penguin07 QQ"(with no quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After catching Suicune, 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 four 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)
4. reverse the order of all the people in the a_i-th row

Now it’s your turn! You need to help them to move and tell Squidward the final formation in the end.

 

Hint for reverse:

1. Easy way , but you can only get 2 more correct answers.

But, you should think another way to accelerate your performance to get AC.

 

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] = {};
 
//reverse(list[i])'s head node
Node *rev_head[100005] = {};
 
//reverse(list[i])'s tail node
Node *rev_tail[100005] = {};
 
/*
list[a] = 1 -> 2 -> 3 -> 4
rev_list[a] = 4 -> 3 -> 2 -> 1
head[a]->val = 1, tail[a]->val = 4
rev_head[a]->val = 4, rev_tail[a]->val = 1
you can use rev_head and rev_tail to get O(1) reverse
*/
 
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)
 
    */

    /*swap(rev_head)
 
    */

    /*swap(rev_tail)
 
    */
}
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] = ...
    ...
    */
}
void reverse(int a) {
    //reverse list[a]
    if(head[a] == NULL) return;
    /*
    use rev_head and rev_tail to reverse list[a] in O(1)
    hint: swap something
    */
}

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 two integer type_i, a_i. If type_i isn't equal to 4, then a integer b_i follows(1 ≤ type_i ≤ 4, 1 ≤ a_i, b_i ≤ N, a_i ≠ b_i) – they are the corresponding information for each moving.

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample #1 below
• For the first three testcases: 1 ≤ N, Q ≤ 10³, the sum of all the sz_i ≤ 10⁴, all the type_i ≠ 4
• For the first six testcases: all the type_i ≠ 4
• For the first eight testcases: the number of the fourth type of moving ≤ 100

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.

 

Note: there are two sample below. "# Sample Input 1/2" and "# Sample Output 1/2" are not the part of input and output.

They are just for marking that the following content corresponds to which sample.

Sample Input  Download

Sample Output  Download

Tags

Discuss