Problem 4355: triangle

The new leadership of the national committee, represented by the coordinators of groups A and B, wishes to maintain a strict syllabus of the given problems for selecting the national team. For this purpose, they will need to give a geometry problem. Moreover – the number of interactive problems given so far are below standard. To fix the crisis in the selection for IOI, Sashka decided to give a problem that is both interactive and geometric. It has the following statement:

The jury has hidden a permutation $P_0, P_1, ..., P_{N-1}$ of $\{1, 2, 3, ..., N\}$ . You must find the permutation. For this purpose, you may ask the jury the following question: “Is it possible to form a triangle with positive area with sides $P_A, P_B, P_C$ ?”

Note that it is known (by the triangle inequality) this is possible if and only if: $P_A+P_B>P_C,P_A+P_C>P_B$ and $P_B+P_C>P_A$

Write a program triangle, containing a function solve, which will be compiled together with the jury program and will communicate with it by asking questions of the type described above. At the end of its execution, it must determine the permutation.

Implementation details

You should implement the solve function:

std::vector<int> solve(int N)

$N$ : length of the permutation.

This function will be called $T$ times per test – once per subtest, each with equal $N$ and it should return the hidden permutation for the subtest. In order to do this, your program can call the jury function query:

bool query(int A, int B, int C)

$A,B,C$ : indices of the sides $P_A, P_B, P_C$ .

The function returns true, if a triangle with positive area with sides $P_A,P_B,P_C$ exists and false, otherwise.

Constraints and clarifications

$N = T = 1 \ 000$

Subtask	Points	Description
1	100	The subtask consists of 1 test with $T = 1 \ 000$ randomly and uniformly sampled from the set of all possible permutations, each of $N = 1 \ 000$

Scoring

Let $Q_{contestant}$ be the average number of queries that your program for one call of solve on the single test, and let $Q_{target} = 8 \ 770$ . Then your score for the problem will be:

\left\{ \begin{aligned} 0 &\quad \text{if } Q_{contestant} > 2 \cdot 10^6 \\ 100 &\quad \text{if } Q_{contestant} \leq Q_{target} \\ 100 \cdot \max \left(0.15, 1 - \sqrt{\smash[b]{1 - \left( \frac{Q_{target}}{Q_{contestant}} \right)^{0.55}}} \right) &\quad \text{if } Q_{contestant} > Q_{target} \end{aligned} \right.

Sample interaction

Contestant action	Jury action
	`solve(4)`
`query(0, 0, 0)`	`true`
`query(0, 1, 2)`	`false`
`query(0, 1, 3)`	`false`
`query(0, 2, 3)`	`true`
`query(1, 2, 3)`	`false`
`return {3, 1, 2, 4};`
	`solve(4)`
`query(0, 1, 2)`	`false`
`query(0, 1, 3)`	`true`
`query(0, 2, 3)`	`false`
`query(1, 2, 3)`	`false`
`return {4, 2, 1, 3};`

Local testing

Input format:

line $1$ : three integers $T$ , $N$ , and $R$ – the number of subtests, the size of the permutations, and the execution mode. If $R=1$ , the local grader will generate uniformly random permutations and will expect a number on the second line – $S$ , which will be the seed for its random generator. If $R=2$ , the input continues as follows:
lines $2$ to $(1 + T)$ : permutations of $\{1, 2, ..., N\}$ .

Output format:

line $1$ : an error message or the average

triangle

Implementation details

Constraints and clarifications

Scoring

Sample interaction

Local testing

Log in or sign up to be able to send submissions!