staringcontest (BOI contest)
Time limit: 1 seconds | Memory limit: 1024 MB | Task type: interactive
Algorithms: randomized algorithms

# Staring Contest
Problem ID: staringcontest

A staring contest is a classical battle of imperturbability in which two people stare into each other's eyes while maintaining a facial expression of assured serenity. The goal is to maintain eye contact for longer than your opponent. The contest ends when one participant breaks composure, typically by looking away, smiling, speaking, or giggling.

As a coach of the national staring contest you need to determine the imperturbability of each of your team's n members for the upcoming world finals. The i-th athlete can maintain eye contact for exactly a<sub>i</sub> seconds, but these values are unknown to you in the beginning. For instance, you could have a team of n = 3 members:

![Staring Contest Image](_page_0_Figure_3.jpeg)

Your goal is to estimate the values a<sub>1</sub>, ..., a<sub>n</sub> using as few staring contests as possible. Clearly, the strength of the strongest athlete can never be determined, so you are allowed to underestimate one of the a<sub>i</sub>.

When athletes i and j compete, the confrontation lasts exactly min(a<sub>i</sub>, a<sub>j</sub>) seconds, at which moment the weaker contestant breaks composure and both contestants start smiling and giggling within a fraction of a second. For instance, if Anna competes against Esther, the contest lasts for 431 seconds. Importantly, to an outside observer the actual winner of the confrontation (in this case, Esther) is impossible to determine, only the duration of the contest is measurable.

Here's an example of athlete data:

| i   | Name   | a<sub>i</sub> |
| --- | ------ | -------- |
| 1   | Anna   | 431      |
| 2   | Esther | 623      |
| 3   | Tony   | 121      |

## Interaction

This is an interactive problem. The interaction begins with you reading a single line containing the integer n. You may then ask queries of the form "? i j" such that 1 ≤ i ≤ n and 1 ≤ j ≤ n and i ≠ j. The response to a query is a single integer: the value min(a<sub>i</sub>, a<sub>j</sub>). The interaction ends with you printing a single line consisting of ! followed by n estimates in the form of integers b<sub>1</sub>, ..., b<sub>n</sub>, separated by spaces. This must be your final line of output.

Your submission is correct if b<sub>i</sub> = a<sub>i</sub> for every contestant i except one, which you may underestimate. To be precise, we require b<sub>i</sub> ≤ a<sub>i</sub> for all 1 ≤ i ≤ n and allow b<sub>k</sub> ≠ a<sub>k</sub> for at most one k.

The interactor is *non-adaptive*, meaning that the a<sub>1</sub>, ..., a<sub>n</sub> are determined before the interaction begins.

## Constraints and Scoring

The number n of athletes satisfies 2 ≤ n ≤ 1500. The imperturbability a<sub>i</sub> of each athlete satisfies 1 ≤ a<sub>i</sub> ≤ 86400, and all a<sub>i</sub> are different. You can use at most 3000 queries; your final line of output, *i.e.*, the line starting with !, is not counted as a query.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

For group 3, your score is the minimum score among all test cases in the group. The score for each test case depends on the number of queries you use; fewer queries are better: Suppose you use q queries. If q ≤ n + 25, then you get the full 80 points. If q > 3000, then you get no points. Otherwise, you get 118.2 - 12 · ln(q - n) points, rounded to the nearest integer. For instance, for n = 1500 and q = 3000, you get 30 points.

| Group | Points | Constraints       |
| ----- | ------ | ----------------- |
| 1     | 9      | n ≤ 50            |
| 2     | 11     | n ≤ 1000          |
| 3     | 0–80  | 1000 < n ≤ 1500 |

## Explanation of Sample Interactions

Sample interaction 1 shows a possible interaction using the above example. Note that Anna's and Tony's strengths are correctly determined. (Esther's can never be determined.)

![Sample Interaction Image](_page_1_Figure_2.jpeg)

Starter code:
interactor.cpp: // Adapted from boi2023_tests/staringcontest/output_validators/validate.py
// Author: HeRaNO

#include "testlib.h"

int main(int argc, char *argv[])
{
	registerInteraction(argc, argv);
	std::vector<int> skills;
	while (!inf.seekEof())
		skills.push_back(inf.readInt());
	int n = skills.size();
	printf("%d\n", n);
	fflush(stdout);

	int q = 0;
	while (true)
	{
		std::string opt = ouf.readToken("[?!]", "opt");
		if (opt == "?")
		{
			++q;
			if (q > 3'000)
				quitf(_wa, "Too many rounds");
			int i = ouf.readInt(1, n, "i");
			int j = ouf.readInt(1, n, "j");
			quitif(i == j, _wa, "Query indices must be different, not both %d", i);
			printf("%d\n", std::min(skills[i - 1], skills[j - 1]));
			fflush(stdout);
		}
		else // opt == "!"
		{
			int errors = 0;
			for (int i = 0; i < n; i++)
			{
				int x = ouf.readInt();
				if (skills[i] < x)
					quitf(_wa, "Expected value <= %d, got %d", skills[i], x);
				if (skills[i] != x)
					++errors;
			}
			if (errors > 1)
				quitf(_wa, "Too many errors (got %d, not 1)", errors);
			break;
		}
	}
	if (n <= 1'000)
		quit(_ok, "");
	else
	{
		int additional_queries = q - n;
		if (additional_queries < 25)
			additional_queries = 25;
		ensure(25 <= additional_queries && additional_queries <= 1'500);
		int score = std::lround(118.2-12*std::log((double)additional_queries));
		ensure(1 <= score && score <= 80);
		if (score == 80)
			quitf(_ok, "");
		else
			quitp((double)score * 5 / 4, "");
	}
	return 0;
}


Grader code:
interactor.cpp: // Adapted from boi2023_tests/staringcontest/output_validators/validate.py
// Author: HeRaNO

#include "testlib.h"

int main(int argc, char *argv[])
{
	registerInteraction(argc, argv);
	std::vector<int> skills;
	while (!inf.seekEof())
		skills.push_back(inf.readInt());
	int n = skills.size();
	printf("%d\n", n);
	fflush(stdout);

	int q = 0;
	while (true)
	{
		std::string opt = ouf.readToken("[?!]", "opt");
		if (opt == "?")
		{
			++q;
			if (q > 3'000)
				quitf(_wa, "Too many rounds");
			int i = ouf.readInt(1, n, "i");
			int j = ouf.readInt(1, n, "j");
			quitif(i == j, _wa, "Query indices must be different, not both %d", i);
			printf("%d\n", std::min(skills[i - 1], skills[j - 1]));
			fflush(stdout);
		}
		else // opt == "!"
		{
			int errors = 0;
			for (int i = 0; i < n; i++)
			{
				int x = ouf.readInt();
				if (skills[i] < x)
					quitf(_wa, "Expected value <= %d, got %d", skills[i], x);
				if (skills[i] != x)
					++errors;
			}
			if (errors > 1)
				quitf(_wa, "Too many errors (got %d, not 1)", errors);
			break;
		}
	}
	if (n <= 1'000)
		quit(_ok, "");
	else
	{
		int additional_queries = q - n;
		if (additional_queries < 25)
			additional_queries = 25;
		ensure(25 <= additional_queries && additional_queries <= 1'500);
		int score = std::lround(118.2-12*std::log((double)additional_queries));
		ensure(1 <= score && score <= 80);
		if (score == 80)
			quitf(_ok, "");
		else
			quitp((double)score * 5 / 4, "");
	}
	return 0;
}


Setup script:

Evaluation script: