13141 - KuoYangてぇてぇ — Birthday Gift   

Status  |  Limits Submit

Description

 

Kuo-chan gives Yang-chan an empty sequence A as his birthday gift.

Yang-chan is allowed to perform the following operation:

  1. PUSH x — push x to the end of A
  2. POP — remove the median value of A if A is not empty
  3. PROGRAMMING TANOSHI k — for 1 ≤ i ≤ |A|, assign ⌈ A[ i ] / k ⌉ (ceil) to A[ i ]
  4. IP2 SUGOI — for 1 ≤ i ≤ |A|, assign ⌊ A[ i ]0.5 ⌋ (floor) to A[ i ]

 

  • the median value of A is A[ (|A|+1)/2 ]
  • ⌈ x ⌉ is the least integer greater than or equal to x
  • ⌊ x ⌋ is the greatest integer less than or equal to x

 

For example, initially A = []

PUSH 4　►　A = [4]

PUSH 3　►　A = [4, 3]

PUSH 5　►　A = [4, 3, 5]

PUSH 11　►　A = [4, 3, 5, 11]

POP　►　A = [4, 5, 11]

POP　►　A = [4, 11]

PROGRAMMING TANOSHI 3　►　A = [2, 4] 

IP2 SUGOI　►　A = [1, 2]

 

Kuo-chan is curious about what A is after Yang-chan performs some operations to it.

Help him find it out!

 

Input

The input contains Q lines.

Initially, A is empty.

Each of the Q lines describes the operations Yang-chan performs. Each line is one of four types:

  1. PUSH x  (1 ≤ x ≤ 109 )
  2. POP
  3. PROGRAMMING TANOSHI k ( 1 ≤ k ≤ 9 )
  4. IP2 SUGOI

 

Different testcases have different constraints.

  1. Q ≤ 2*103, operations: { PUSH, POP }
  2. Q ≤ 2*103, operations: { PUSH, POP, PROGRAMMING TANOSHI }
  3. Q ≤ 2*103, operations: { PUSH, POP, PROGRAMMING TANOSHI, IP2 SUGOI }
  4. Q ≤ 3*105, operations: { PUSH, POP }
  5. Q ≤ 3*105, operations: { PUSH, POP, PROGRAMMING TANOSHI }
  6. Q ≤ 3*105, operations: { PUSH, POP, IP2 SUGOI }
  7. Q ≤ 3*105, operations: { PUSH, POP, PROGRAMMING TANOSHI, IP2 SUGOI }
  8. Q ≤ 3*105, operations: { PUSH, POP, PROGRAMMING TANOSHI, IP2 SUGOI }

Note: You can include <math.h> to use sqrt(x). sqrt(x) returns the square root of x. Just be careful with roundoff error.

          You can also use ceil(x), floor(x) included in <math.h>.

Hint: To speed up the code, you can think about how many operations will an element be performed at most.

Update: 1.  Make use of  the variable all_operation to store {PROGRAMMING TANOSHI, IP2 SUGOI} operations.

              2. You can think that if a number becomes 1  you won't need to do any operation on it anymore.

Output

You should print one line containing the elements of A after the operations. For 1 ≤ i ≤ |A|, the i-th number should be A[ i ].

Sample Input  Download

Sample Output  Download

Partial Judge Code

13141.c

Partial Judge Header

13141.h

Tags




Discuss