408678: GYM103261 E Binary Search Algorithm
Description
This is an interactive problem.
I have a hidden permutation $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$. You are not to guess it. Your task is to devise a data structure (that's against the rules!) that supports the following operations on a set $$$S$$$, which is initially empty:
- "add $$$x$$$" — put element $$$x$$$ in $$$S$$$,
- "delete $$$x$$$" — delete element $$$x$$$ from $$$S$$$,
- "getMin" — print the element $$$x$$$ from $$$S$$$ such that $$$p_x$$$ is the smallest among $$$x$$$ in $$$S$$$.
You will have to perform "getMin" after each operation of other types.
You don't know the permutation, but you can make queries. In one query you can choose $$$k$$$ distinct indices $$$x_1$$$, $$$x_2$$$, ..., $$$x_k$$$ for some value of $$$k$$$, and in return I will tell you the permutation of these indices $$$y_1$$$, $$$y_2$$$, ..., $$$y_k$$$ such that $$$p_{y_1} < p_{y_2} < \ldots < p_{y_k}$$$. In other words, I will sort the indices according to $$$p$$$.
Note that all $$$x_i$$$ should be present in $$$S$$$ at the moment of query.
It is easy to perform "getMin" in $$$1$$$ query — just sort everything in $$$S$$$. It is also not hard to perform it using several queries with sum of $$$k$$$ up to $$$O(\log n)$$$. Can you flex your algorithm (this is lame) muscles and satisfy both?
Note that since you don't know $$$p$$$ and my task is to make your solution fail, I can change $$$p$$$ depending on your queries, but only in such a way that all my previous responses are correct. I can also choose the order of operations you have to perform depending on your queries.
InputInitially you are given a single line with one integer $$$n$$$ ($$$1 \le n \le 8000$$$) — the number of elements. Each element will be inserted and deleted exactly once.
InteractionThen there will be exactly $$$2n$$$ rounds of interaction.
Each round of interaction consists of $$$4$$$ phases:
- you read the next operation on a separate line: either "add $$$x$$$" or "delete $$$x$$$" for some $$$1 \le x \le n$$$;
- you choose some $$$0 \le k \le \min(|S|, 30)$$$ and print $$$k + 1$$$ numbers on a separate line: $$$k$$$ first, then $$$x_1$$$, $$$x_2$$$, ..., $$$x_k$$$: the $$$k$$$ elements you want to sort. Elements you choose should be between $$$1$$$ and $$$n$$$, should be distinct, and should be in $$$S$$$ at this time. Note that $$$S$$$ is already changed according to phase 1;
- you read $$$k$$$ integers $$$y_1$$$, $$$y_2$$$, ..., $$$y_k$$$ on a separate line: $$$y$$$ is a permutation of $$$x$$$ you just printed, and $$$p_{y_1} < p_{y_2} < \ldots < p_{y_k}$$$;
- you print a single integer $$$x$$$ on a separate line, such that $$$x$$$ is in $$$S$$$, and $$$p_x$$$ is the smallest possible. Print $$$-1$$$ if $$$S$$$ is empty.
It is guaranteed that all $$$2n$$$ possible operations ("add $$$x$$$" and "delete $$$x$$$" for all $$$1 \le x \le n$$$) will occur exactly once, and for each $$$x$$$ operation "add $$$x$$$" will precede "delete $$$x$$$".
Do not forget to print end of line and flush your output before you read anything.
ExampleInput3 add 1 1 add 3 3 1 delete 1 3 add 2 3 2 delete 3 2 delete 2Output
1 1 1 2 1 3 3 1 3 3 2 2 3 3 1 2 2 0 -1Note
In the example $$$p = [2, 3, 1]$$$.