Yet Another Frog Jumping Problem

tbs_sajal15 BUET Inter University Pro...
Limits 4s, 512 MB · Interactive

This is an interactive problem. (If you want to know about interactive problems, click here)

There are NN stones. Stones are enumerated from 11 to NN. There is an intelligent frog too. Jumping capability of the frog never decreases, but it may change at most 3939 times. If his jumping capability is DD on a given day, he can go exactly to stone x+Dx+D from stone xx in a valid jump, if x+Dx+D is not greater than NN.

Initially, all of the stones are uncolored. The frog wishes to color all of the stones. Every morning, the frog discovers himself in the first uncolored stone (i.e. uncolored stone with smallest index). During that whole day, his jumping capability does not change and he keeps jumping as long as it can. Whenever he reaches an uncolored stone, he colors it with color DD if his jumping capability is DD during that day. However, the frog is clever. Whenever he reaches an already colored stone, he does not color it again and keeps moving (Note that he must color initial stone of that day). He stops jumping for that day, only if jumping from his current stone is not valid.

Whenever all of the stones are colored, the frog goes back to play with his friends.

You do not know the number of days to complete the task, you do not even know the jumping capability of the frog each day. You can do 720720 queries, asking for color of a stone.

Retrieve the number of days to complete the task and color of every stone.


First line contains an integer TT (1T1000)(1 \le T \le 1000), the number of test cases. For each case, first line contains an integer NN (1N105)(1 \le N \le 10^5), the number of stones.

Sum of NN over all test cases does not exceed 10610^6.


You can ask at most 720720 queries for each test case. To ask a query just print an integer, ii (1iN)(1 \le i \le N), then read an integer CC (1C109)(1 \le C \le 10^9), the color of the stone ii. There will be at most 4040 distinct colors for each test case.

When you can determine the color of all stones print 00 (which is not counted as a query). In the next line, print the number of days the frog needed to color all stones. In the next line print NN integers, separated by spaces, C1,C2,,CNC_1, C_2,\cdots,C_N where CiC_i is the color of stone ii.

After that read an integer, resres. If resres is 1-1, then it means your output is wrong for that test case and you should terminate the program immediately and you will receive Wrong Answer verdict. If resres is not 1-1, then process the next test case. If at any moment the number of query asked is greater than 720720 or an invalid query is asked, then you will receive an integer 1-1 and you should terminate the program immediately and you will receive Wrong Answer verdict.

Imagine a valid example, where T=1T=1, N=5N=5 and colors of the stones are [2,3,2,3,2][2,3,2,3,2].

Interaction may happen as ,









<< 22 33 22 33 22


It takes the frog 33 days to complete.

>> indicates what your program reads and << indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.


Login to submit.


20% Solution Ratio
MrBrionixEarliest, 5d ago
MrBrionixFastest, 1.0s
MrBrionixLightest, 2.0 MB
MrBrionixShortest, 1529B
Toph uses cookies. By continuing you agree to our Cookie Policy.