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:

This’s the sample code of ReadOneList, PrintList, Cut from TA.
Merge is the only function you have to implement.
If you don’t like TA’s code, just implement them by yourself.

#include "function.h"
#include <stdio.h>
#include <stdlib.h>

Node* CreateNode(int size){
    Node* n = (Node*) malloc( sizeof(Node) );
    n->size = size;
    n->data = (int*) malloc( sizeof(int) * size );
    n->next = NULL;
    return n;
}

Node* ReadOneList(){
    int Ni;
    scanf("%d:", &Ni );
    Node* new_node = CreateNode(Ni);
    for(int i=0; i<new_node->size; i++){
        scanf(" %d", &(new_node->data[i]) );
    }
    return new_node;
}

void PrintList(Node* dummy_head){
    Node* cur = dummy_head->next;
    while( cur != NULL ){
        printf("%d", cur->data[0]);
        for(int i=1; i<cur->size; i++){
            printf(" %d", cur->data[i]);
        }
        printf("\n");
        cur = cur->next;
    }
}
void Merge(Node* dummy_head, int x, int y){
    // Your work
}
void Cut(Node* dummy_head, int x, int idx){
    Node* prev_x = dummy_head;
    Node* list_x = dummy_head->next;
    while( --x ) list_x = list_x->next, prev_x = prev_x->next;

    int size_x1 = idx, size_x2 = list_x->size - size_x1;
    Node* list_x1 = CreateNode( size_x1 );
    Node* list_x2 = CreateNode( size_x2 );
    
    for(int i=0; i<list_x1->size; i++)
        list_x1->data[i] = list_x->data[i];
    for(int i=0; i<list_x2->size; i++)
        list_x2->data[i] = list_x->data[i + list_x1->size];
    
    prev_x->next = list_x1;
    list_x1->next = list_x2;
    list_x2->next = list_x->next;

    free(list_x->data);
    free(list_x);
}

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 ≤ 10⁴
• ∑ Ni ≤ 2∗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

12695.c

Partial Judge Header

12695.h

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