## DMOPC '23 Contest 1 P3 - Colour Scheme

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type

There is a hidden array of size , where represents the colour of the th element. You are allowed at most questions. In each question, you can query a range and get the number of distinct colours in that range. Find an array such that the colour scheme of is equivalent to the colour scheme of . That is, for any pair , either and , or and must hold.

For example, and have an equivalent colour scheme.

#### Interaction

This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.

At first, you should read in a line containing the integer .

You will then start the interaction by proceeding with your queries.

Each query should be formatted as ? l r followed by a \n character, with .

In response, the judge will return an integer on its own line, whose value is the number of distinct integers in the range of the hidden array .

If you believe you have the solution, you may output ! followed by a space-separated list of integers , , an array which has an equivalent colour scheme to the hidden array . You must terminate your program immediately after performing this operation. Note that this operation does not count towards the query limit of .

If at any point you attempt an invalid question (such as an invalid output format or an invalid range), or you exceed the query limit , the judge will respond with . You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict. If the final list you output is incorrect, you will receive a Wrong Answer verdict. Otherwise, you will receive a verdict of Accepted for the corresponding test case.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

#### Scoring

If you have received a verdict of Accepted, your score for the test case will be calculated as follows, where is the number of queries that you used.

Score
points
points
points

Your score for a batch is the minimum of the scores of all of the tests in the batch.

#### Sample Interaction

>>> denotes your output. Do not print this out.

Here, the hidden array is . One of the possible valid arrays is .

3
>>> ? 1 2
2
>>> ? 1 3
3
>>> ? 2 3
2
>>> ! 3 2 1