Codeforces Round 385 (Div. 1)
B
Hongcow's Game
Codeforces
1900
原题
← AC →
翻译中…

This is an interactive problem. In the interaction section below you will see the information about flushing the output.

翻译中…

In this problem, you will be playing a game with Hongcow. How lucky of you!

翻译中…

Hongcow has a hidden $*n*$ by $*n*$ matrix $*M*$. Let $*M*_{*i*, *j*}$ denote the entry $*i*$-th row and $*j*$-th column of the matrix. The rows and columns are labeled from $1$ to $*n*$.

翻译中…

The matrix entries are between $0$ and $10^{9}$. In addition, $*M*_{*i*, *i*} = 0$ for all valid $*i*$. Your task is to find the minimum value along each row, excluding diagonal elements. Formally, for each $*i*$, you must find image.

翻译中…

To do this, you can ask Hongcow some questions.

翻译中…

A question consists of giving Hongcow a subset of distinct indices ${*w*_{1}, *w*_{2}, ..., *w*_{*k*}}$, with $1 ≤ *k* ≤ *n*$. Hongcow will respond with $*n*$ integers. The $*i*$-th integer will contain the minimum value of $*min*_{1 ≤ *j* ≤ *k*}*M*_{*i*, *w*_{*j*}}$.

翻译中…

You may only ask Hongcow at most $20$ questions — he thinks you only need that many questions answered.

翻译中…

When you are ready to answer, print out a single integer $- 1$ on its own line, then $*n*$ integers on the next line. The $*i*$-th integer should be the minimum value in the $*i*$-th row of the matrix, excluding the $*i*$-th element. Do not forget to flush the final answer as well. Printing the answer does not count as asking a question.

翻译中…

You will get Wrong Answer verdict if

翻译中…
  • Your question or answers are not in the format described in this statement.
  • You ask strictly more than $20$ questions.
  • Your question contains duplicate indices.
  • The value of $*k*$ in your question does not lie in the range from $1$ to $*n*$, inclusive.
  • Your final answer is not correct.
翻译中…

You will get

翻译中…

Idleness Limit Exceeded

翻译中…

if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).

翻译中…

Input

翻译中…

The first line of input will contain a single integer $*n*$ ($2 ≤ *n* ≤ 1, 000$).

翻译中…

Output

翻译中…

To print the final answer, print out the string -1 on its own line. Then, the next line should contain $*n*$ integers. The $*i*$-th integer should be the minimum value of the $*i*$-th row of the matrix, excluding elements on the diagonal. Do not forget to flush your answer!

翻译中…

Interaction

翻译中…

To ask a question, print out a single integer $*k*$ on its own line, denoting the size of your subset. Then, the next line should contain $*k*$ integers $*w*_{1}, *w*_{2}, ... *w*_{*k*}$. Note, you must flush your output to get a response.

翻译中…

Hongcow will respond by printing out a line with $*n*$ integers. The $*i*$-th integer in this line represents the minimum value of $*M*_{*i*, *w*_{*j*}}$ where $*j*$ is between $1$ and $*k*$.

翻译中…

You may only ask a question at most $20$ times, otherwise, you will get Wrong Answer.

翻译中…

To flush you can use (just after printing an integer and end-of-line):

翻译中…
  • fflush(stdout) in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal;
  • See the documentation for other languages.
翻译中…

Hacking To hack someone, use the following format

翻译中…

n
M_{1,1} M_{1,2} ... M_{1,n}
M_{2,1} M_{2,2} ... M_{2,n}
...
M_{n,1} M_{n,2} ... M_{n,n}

翻译中…

Of course, contestant programs will not be able to see this input.

翻译中…

Note

翻译中…

In the first sample, Hongcow has the hidden matrix

翻译中…

[
 [0, 3, 2],
 [5, 0, 7],
 [4, 8 ,0],
]

翻译中…

Here is a more readable version demonstrating the interaction. The column on the left represents Hongcow, while the column on the right represents the contestant.

翻译中…

3
              3
              1 2 3
0 0 0
              1
              3
2 7 0
              2
              1 2
0 0 4
              1
              2
3 0 8
              1
              1
0 5 4
              -1
              2 5 4

翻译中…

For the second sample, it is possible for off-diagonal elements of the matrix to be zero.

翻译中…

样例

Input #1
3
0 0 0
2 7 0
0 0 4
3 0 8
0 5 4
Output #1
3
1 2 3
1
3
2
1 2
1
2
1
1
-1
2 5 4
InputCopy OutputCopy
Input #2
2
0 0
0 0
Output #2
1
2
1
1
-1
0 0
InputCopy OutputCopy
题目信息
题号
744B
时间限制
3 s
内存限制
256 MB
标签
位运算
分治
交互题

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。