Altar 2 (altar)

This is an interactive problem.

Background

A year has passed, and Altar stands before the altar he once destroyed. The gems on the altar have long since lost their original luster.

"The one who tied the bell must be the one to untie it, is that so?" he muttered to himself.

Description

The altar is a regular $n$-sided polygon, with an inactive gem at each vertex. We label each type of gem with an integer from $1$ to $n$.

There exists an energy flow relationship between the gems, which makes it easier to activate other gems once some gems are activated. For every pair of gems $(i, j)$ ($i \neq j$), there is either a flow from $i$ to $j$ or from $j$ to $i$. That is, if we treat the gems as vertices and the flow from $p$ to $q$ as a directed edge from $p$ to $q$, the resulting graph is a tournament graph with $n$ vertices. Altar does not know the energy flow relationships between the gems.

To activate the altar, Altar needs to activate all the gems. To do this, Altar must first choose one of the $n$ gems to activate initially, and then perform several energy propagations. The effect of each energy propagation is: if a gem $y$ is not activated before this propagation, and there exists an activated gem $x$ such that there is a flow from $x$ to $y$, then $y$ will be activated after the propagation. Gems that were already activated before the propagation remain activated after the propagation.

Since energy propagation consumes a large amount of physical strength, Altar hopes to find a gem that, when initially activated, allows all gems to be activated using the minimum number of energy propagations. To this end, Altar can perform several energy sensing operations: given $1 \le i, j \le n$ and $i \neq j$, one energy sensing operation can determine the energy flow relationship between gem $i$ and gem $j$.

You need to help Altar use as few energy sensing operations as possible to determine the index of the gem to initially activate. It can be proven that there always exists a gem such that, if it is initially activated, all gems can be activated using a finite number of energy propagations.

Implementation Details

Ensure that your program starts with #include "altar.h".

You do not need to, and should not, implement the main function. You need to implement the following function:

int altar(int n);

• $n$ represents the number of gems on the altar.
• You need to return an integer $x$, representing the gem Altar needs to initially activate. You must ensure $1 \le x \le n$, and that among all gems, initially activating $x$ allows Altar to activate all gems using the minimum number of energy propagations.
• In the final tests, the interactor will call the altar function $T = 300$ times in a single run.

You can call the following function to perform energy sensing:

bool sense(int i, int j);

• You must ensure $1 \le i, j \le n$ and $i \neq j$.
• If the energy flow is from $i$ to $j$, it returns true, otherwise it returns false.
• You must ensure that the number of calls to sense in a single call to altar does not exceed $4.5 \times 10^4$.

Under the given constraints and data ranges, the running time of the interactor in the final tests will not exceed $150\text{ ms}$, and the memory usage will not exceed $256\text{ MiB}$.

The interactor is not adaptive, meaning the energy flow relationships are fixed and will not change during the interaction process.

Testing Procedure

The grader.cpp in the problem directory is our provided reference implementation of the interactor. The final testing interactor is different from the sample interactor, so your implementation should not rely on the sample interactor's implementation.

You need to compile the executable in the problem directory using the following command:

g++ grader.cpp sample.cpp -o sample -O2 --std=c++14 -lm

For the compiled executable:

• The executable will read data from standard input in the following format:
  • The first line contains an integer $n$ representing the number of gems on the altar, where $3 \le n \le 300$.
  • The next $n$ lines each contain a $01$ string of length $n$, where the $j$-th ($j \neq i$) character being $1$ indicates an energy flow from $i$ to $j$, otherwise it indicates a flow from $j$ to $i$. You must ensure that for the $j$-th character of the $i$-th line and the $i$-th character of the $j$-th line, exactly one is $1$ and the other is $0$.
• After reading is complete, the interactor will call the altar function exactly once.
• After the altar function returns, if you provided the correct gem index, the interactor will output Correct. X to the standard output, where $X$ is the number of sense calls, and output the gem index you returned and the corresponding number of energy propagations to the standard error stream; otherwise, the interactor will output Wrong Answer to the standard output and output the corresponding error message to the standard error stream.

Examples

Input 1

4
0011
1010
0000
0110

Output 1

Correct. 1
You report 2, with number of energy propagations to be 2

Note 1

The output above is the output of the provided sample program for this set of examples. In this example, returning $1, 2,$ or $4$ from altar all satisfy the conditions.

Subtasks

For all test data, the number of calls to the altar function in a single test point is $T = 300$, and for each call, $3 \le n \le 300$.

• Subtask 1 (10 points, 1 test point): $n = 300$, the energy flow direction between any two gems is chosen independently and uniformly at random between the two possibilities.
• Subtask 2 (10 points, 2 test points): There exists a gem that flows to all other gems.
• Subtask 3 (80 points, 7 test points): No special restrictions, depends on Subtasks 1 and 2.

Scoring

This problem is subject to the same restrictions as traditional problems; for example, compilation errors result in 0 points for the entire problem, while runtime errors, time limit exceeded, or memory limit exceeded result in 0 points for the corresponding test point. You may only access variables or data defined by yourself or provided by the interactor, and their corresponding memory space. Attempting to access other memory locations may result in compilation or runtime errors.

For each test point, if your program makes an illegal function call or fails to return the correct gem in all test cases, you will receive 0% of the score for that test point. Otherwise, your score percentage for that test point will be calculated based on the average number of sense calls $X$ over the $T$ calls to altar, using the following formula:

• If $45000 \ge X \ge 10^4$, you receive $\left(1 + 29 \times \frac{45000-X}{35000}\right)\%$ of the score;
• If $10^4 > X \ge 2100$, you receive $\left(30 + 30 \times \frac{10^4-X}{7900}\right)\%$ of the score;
• If $2100 > X \ge 700$, you receive $\left(60 + 20 \times \frac{2100}{X} - 1\right)\%$ of the score;
• If $X \le 700$, you receive 100% of the score for that test point.

The score for each subtask is the product of the minimum score percentage among all test points in that subtask and the total points for that subtask.

Participants must not obtain internal information about the interactor through illegal means, such as attempting to interact with standard input/output streams. Such behavior will be considered cheating.