Description

Forevernight is playing cards with his friend SugarHao in their new apartment Mèng Zhú public housing (孟竹國宅).

As a CS student, he wants to play it in a programmer way. He decides to write a program for the purpose of shuffling the cards. Moreover, since Forevernight is really famous in their department, more friends may come while he is shuffling cards, so sometimes he needs to insert new cards into the card stack, too.

In view of the fact that he's taking I2P(II) this semester, his another friend Jason(one of the TAs) commands that he should write the program in a C++ way.

Note: This is a patial judge problem. You're asked to implemet 5 functions in this problem.

1. Card* Construct(int N) - This function would create a linked list with N elements, each node (ie. card) contains a number given by testcase serially in one single line. (Noted that you should get the number from the input by std::cin or scanf on your own.) The function should return a pointer to the first element of the linked list. Warning: To improve your C++ skills, you should only use C++ operator new to allocate your Card node. We will use another function void Destruct(Card* head) using delete to deallocate the space.
2. void add(int idx, int num, Card* head) - This function should add a new card with number num before card idx.
3. void cut(int a, int b, Card* head) - This function should move cards whose index between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part shouldn't be changed.
4. void reverse(int a, int b, Card *head) - This function should reverse the order of cards whose index between a and a+b-1 ( [a, a+b) ).
5. void print(Card* head) - This function should print out the card list from top (index 0) to buttom (largest index), each number followed by a newline character '\n'.

Input

First line of input contains two integer \(n\), \(m\), representing # of cards in the beginning and # of operations.

Next line contains \(n\) integers \(c_1, c_2, \cdots, c_n\), representing the number on each card from the top (index 0) to the buttom (index n-1).

Each of the next \(m\) lines contains an operation. Operations begin with ADD, CUT or REVERSE.

• ADD idx num: Add a new card with number num before card idx.
• CUT a b: Move cards whose index between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part won't be changed. Index of a card means # of cards on the top of that card. It may change after operations.
• REVERSE a b: Reverse the order of cards whose index between a and a+b-1 ( [a, a+b) ).

Constraints

• \(1 \le n, m \le 10^4\)
• \(0 \le c_i \le 10^9\)
• \(0 \le a, b, idx\)
• In CUT operation, card with index = a+b-1 always exists.
• In REVERSE operation, card with index = a+b-1 always exists.

Operation in each testcase:

1. {ADD}
2. {CUT}
3. {REVERSE}
4. {ADD, CUT}
5. {ADD, CUT, REVERSE}
6. {ADD, CUT, REVERSE}
7. {ADD, CUT, REVERSE}
8. {ADD, CUT, REVERSE}

Output

Print out the card stack from top (index 0) to buttom (largest index), each number occupies one line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14268.cpp

Partial Judge Header

14268.h

Tags

Discuss