| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9093 | Move |
|
| 9094 | Doubly Linked List |
|
Description
There are N numbers in a queue. The origin sequence is from 1 to N. (1 is the head). The operation “Move a b” means to move all the numbers in front of a (including a) and then insert them in front of b without changing order. Given several such operations and output the final status of the sequence.
Input
There will be only one test case. The test case begins with an integer N (1 <= N <= 106) indicating the number of people. There are several operations followed. The format is “Move a b” (without quote) you can assume that the position of a is in front of the position of b. The test case is terminated by “Exit” (without quote).
Output
Output the numbers from the first one to the last one, and separate two consecutive numbers by a space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Maintain a doubly linked list, which supports the following operations:
(1) IH i : Insert a new integer i to the head of the list.
(2) IT i : Insert a new integer i to the tail of the list.
(3) RH : Print and remove the element in the head of the list.
(4) RT : Print and remove the element in the tail of the list.
(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.
To improve the performance, it is suggested that three pointers be maintained: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.
Input
There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains no more than 500000 operations, and it is terminated by end-of-file (EOF). You may assume that i will fit in a 32-bit signed integer. The list is initially empty.
Output
For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.