#P12635. [UOI 2020] Guess the Color

    ID: 14184 远端评测题 6000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2020交互题Special JudgeUOI(乌克兰)

[UOI 2020] Guess the Color

题目描述

Given nn balls numbered from 11 to nn. Each ball has its own color, which you do not know. There are kk different colors in total.

You can look at a ball in one query and find out the number of balls of the same color that you have already seen (including this one). You will not know the color of the ball itself with such a query. In total, such a query can be made no more than cc times.

You need to find an array colorscolors of nn elements, where each element --- an integer from 11 to kk such that colors[i]=colors[j]colors[i]=colors[j] if and only if balls with numbers ii and jj of the same color.

输入格式

Interaction

The first line contains four integers nn, kk, cc, and gg (1kn1041 \leq k \leq n \leq 10^4) --- the number of balls, the number of colors, the maximum number of queries, and the block number, respectively. See the constraints on cc below.

You can make no more than cc queries. To make a query, you need to output the number 11 and the number indexindex (1indexn1 \leq index \leq n) in one line --- the position of the ball you want to look at. After that, you need to output the end of line character and perform the 'flush' operation. Only after that can you read the answer.

When you already know the answer --- you need to output the number 22 and nn integers of the array colorscolors, where each element is from 11 to kk. After that, you need to output the end of line character, perform the 'flush' operation, and terminate the program.

输出格式

See Interaction

5 3 100 0
0
0
1
1
0
2
3
1 1
1 2
1 3
1 4
1 5
1 1
1 3
2 1 2 1 2 3

提示

Let n=5n=5, k=3k=3, c=100c=100 and a=[2 1 2 1 3]a = [2\ 1\ 2\ 1\ 3].

If you look at a ball 11, you will get a value of 11. If you look at the ball 11 again, the value will be 22. Now, if you look at the ball 22, the value will be 11. Then for 33 ball --- we get 33. For 44 ball --- we get 22. For 55 ball --- we get 11.

After that, the array [2 3 2 3 1][2\ 3\ 2\ 3\ 1] can be returned. This answer will be correct.

Scoring

  • (77 points) n104n \le 10^4; k=n1k = n-1; c=5104c = 5 \cdot 10^4; there are two balls of the same color, and the rest of the balls are of different colors;
  • (77 points) n104n \le 10^4; k=2k = 2; c=5104c = 5 \cdot 10^4;
  • (1010 points) n500n \le 500; knk \le n; c=3105c = 3 \cdot 10^5;
  • (1414 points) n104n \le 10^4; k10k \le 10; c=3105c = 3 \cdot 10^5;
  • (1515 points) n104n \le 10^4; knk \le n; c=2104c = 2 \cdot 10^4; for each color from 11 to kk, the number of balls of this color is different; each color occurs at least once;
  • (up to 4747 points) n104n \le 10^4; knk \le n; c=4106c = 4 \cdot 10^6:
    • 77 points if you use no more than 41064 \cdot 10^6 requests;
    • 1717 points if you use no more than 10610^6 requests;
    • 3232 points if you use no more than 61056 \cdot 10^5 requests;
    • 4747 points if you use no more than 31053 \cdot 10^5 requests;