Canadian Computing Competition: 2009 Stage 2, Day 2, Problem 1

You have $N$ $(1\le N\le 10000)$ caps and $N$ bottles. Each bottle has a unique size and each cap corresponds to a single bottle. Unfortunately, the caps and bottles are so close together in size that it is impossible to compare them visually.

The only comparison that we can make is between a cap and a bottle. We do this by attempting to put the cap on the bottle. From this, we know whether the cap is too small, too large, or just the right size in relation to the bottle.

Match all the caps to their corresponding bottles as quickly as possible by interacting with a library that compares the pieces.

You may make at most $500000$ queries.

In $20\mathrm{\%}$ of the test cases, $N\le 700$.
In another $40\mathrm{\%}$ of the test cases, $N\le 3000$.

Interactive Instructions

The first line contains the integer $N$.

Afterwards, you must start interaction.

To query, output 0 capid bottleid. You will receive a 1 if the cap is too large for the bottle, 0 if the cap fits the bottle, and -1 if the cap is too small for the bottle.

To report, output 1 capid bottleid. You will not receive anything back from the interactor.

You may interlace reports and queries. Once you have reported $N$ times, your solution must exit. Otherwise, your result is undefined. Only queries (type 0) count towards your $500000$ query limit.

Note: Up to 3s of the time limit may be taken up by the interactor.

The grader is NOT adaptive.

Sample Interaction

The cap sizes are: $[2,1,3]$. The bottle sizes are: $[3,2,1]$. >>> denotes your output. Do not print this out.

3
>>> 0 1 1
-1
>>> 0 1 2
0
>>> 0 1 3
1
>>> 1 1 2
>>> 0 2 1
-1
>>> 1 3 1
>>> 1 2 3

Description of Sample Interaction

There are three caps and three bottles. The first, second and third cap match the second, third, and first bottle, respectively.