Hocky Yudhiono

hello

2 minute read

P14134 【MX-X22-T5】「TPOI-4E」Get MiN? Get MeX!

Problem Description

This is an interactive problem.

There exists a hidden permutation $a_1, \ldots, a_n$ of the range $0\sim n-1$. This permutation is predetermined before you begin making queries and remains unchanged throughout your interactions. You may perform a limited number of queries on this permutation:

  • Given a set $S$, the interactive library returns the value of $\min_{x\in S}a_x+\operatorname*{mex}_{x\in S}a_x$. You may use this query type up to $35$ times.

  • Given a set $S$, the interactive library returns the value of $\min_{x\in S}a_x-\operatorname*{mex}_{x\in S}a_x$. This type of query may be used at most once.

$\operatorname*{mex}_{x\in S}a_x$ denotes the smallest non-negative integer that has not yet appeared in the set ${ a_x \mid x \in S }$.

After the queries, you must compute the position of the zero in the permutation.

Input Format

See [Output Format].

Output Format

You must read a positive integer $n$ from standard input, representing the length of the permutation.

For the first type of query, output to standard output a single character ?, an integer $1$, an integer $len$, and $len$ distinct integers $S_i$ ($1 \le S_i \le n$). Note that this query type may appear at most $35$ times.

For the second type of query, you must output to standard output a single character ?, an integer $2$, an integer $len$, and $len$ distinct integers $S_i$ ($1 \le S_i \le n$). Note that this query type may appear at most once.

Then you must flush the buffer. You may use the following statements to flush the buffer:

  • C++: fflush(stdout);
  • Java: System.out.flush();
  • Python: stdout.flush();
  • Pascal: flush(output);
  • For other languages, refer to the relevant documentation.

Next, you must read an integer from standard input, representing the result returned by the evaluation system.

After the query ends, you must first output the character ! to standard output, followed by an integer $p$ indicating the position of $0$ in the permutation. After outputting this, your program should immediately terminate.

If at any point your program reads $-10^9$ as an answer, it should exit immediately (e.g., by calling exit(0)). In this case, you will receive a “Wrong Answer” result, indicating your question exceeded limits or was invalid. Ignoring this may lead to other judgments due to your program continuing to read from closed streams.

Sample Input/Output #1

Input #1

6
4
2
1
-1

Output #1

? 1 5 1 2 3 4 5
? 1 4 1 2 5 6
? 1 1 3
? 2 1 3
! 3

Notes/Hints

【Sample Explanation】

Samples are provided solely to demonstrate the interactive format; the rationality of the sample output strategy is not guaranteed.

The hidden permutation is $a = [5,2,0,1,3,4]$.

【Data Range】

This problem employs bundled testing.

Subtask ID $n \le$ Special Properties Points Subtask Dependencies
$1$ $1$ None $1$ None
$2$ $2$ ^ $2$ None
$3$ $3$ ^ $3$ None

Translated with DeepL.com (free version)

You may also enjoy