## Binary Search Tree Test

View as PDF

Points: 20
Time limit: 2.5s
Java 4.5s
Racket 4.5s
Memory limit: 1G

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Xyene is doing a contest. He comes across the following problem:

You have an array of elements. There are operations you need to perform on it.

Each operation is one of the following:

• I v Insert into the array.
• R v Remove a single element from the array with a value of , if it exists.
• S v Output the smallest element in the array. It is guaranteed that does not exceed the size of the array.
• L v Output the index, starting from , of the first occurrence of in the array, if the array was sorted. Output if is not present in the array.

After all of the operations, print out all of the elements remaining in the array in non-decreasing order.

To enforce performing operations in an online manner, will be encrypted.

At any time, every element in the array is between and , inclusive.

Xyene knows that one fast solution uses a Binary Search Tree. However, he knows that a standard binary search tree has a worst case runtime of per operation. He practices different data structures every day, but still somehow manages to get them wrong. Will you show him a working example?

Not a binary search tree.

#### Input Specification

The first line has and .

The second line has integers, the original array.

The next lines each contain an operation in the format C x, where is the type of operation. is encrypted: you should decode it by finding , where is the answer to the previous S or L operation (or if neither operation has occurred). You should perform the operation using . denotes the bitwise XOR operation.

#### Output Specification

For each S or L operation, output the answer on its own line.

After all operations have been finished, output all of the elements in the final array in non-decreasing order on a single line.

#### Sample Input

5 8
9 4 8 11 2
S 4
I 1
S 13
R 10
L 10
L -5
I 8
L 8

#### Sample Input (Not Encrypted)

For your convenience, here is a version of the sample input that is NOT encrypted. Remember, all of the real test files will be encrypted (like the input above).

5 8
9 4 8 11 2
S 4
I 8
S 4
R 2
L 2
L 4
I 9
L 9

#### Sample Output

9
8
-1
1
4
4 8 8 9 9 11

• commented on Aug. 13, 2018, 10:31 a.m. edited

You said it's welcomed to use map or policy based ds when i sumbited beside ac there is (cheater) and 0 points why ?

• commented on Aug. 13, 2018, 1:35 p.m.

#### Backstory:

A week after ZQFMGB12 uploaded the problem, bruce pointed out that this could be solved using policy-based data structures. So ZQFMGB12 tried to prevent people from using this.

A few weeks later, I managed to get in a submission that used policy-based data structures which avoided detection, rendering it moot.

#### The Present

Fast-forward a year, and the checker still stands as a relic of the past. The challenge of using policy-based data structures is now in avoiding detection.

Hint: The detection system works by piping your code in through stdin to either a gcc or clang process, which has the flags -E -DONLINE_JUDGE -xc++ -Wall -O2 -lm -march=native -s

• commented on July 17, 2018, 9:03 p.m.

The picture says "not a binary search tree", but I checked it at least five times and I swear it's a binary search tree.

• commented on March 31, 2020, 8:29 p.m.

Although I'm also fairly sure that is a binary search tree. This problem requires more than a binary search tree to solve, for the select and rank queries, it needs an order statistic tree.

• commented on Aug. 5, 2017, 10:34 a.m.

I don't understand how 4 xor 1 (from the sample input) is equal to 8 (from the decoded sample input). Can someone please explain?

• commented on Aug. 6, 2017, 1:14 a.m.

It's xor the last answer, not the last input.

• commented on Aug. 6, 2017, 10:33 a.m.

For some reason, I thought it meant the answer to the last xor operation, which was what confused me. Thanks for the clarification!

• commented on June 22, 2017, 7:27 p.m.

Can you use a map?

• commented on June 23, 2017, 12:00 a.m.

You are welcome to use anything, including this.

• commented on April 3, 2017, 1:00 p.m.

Is the first test the same as the sample?

• commented on April 3, 2017, 1:25 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.