strangedevice2

Strange Device

Vasya enjoys solving quizzes. He found a strange device and wants to know how it works.

This device is encrypted with a tree (a connected undirected graph without cycles) with n vertices, numbered with integers from 1 to n. To solve this quiz you should guess this tree.

Fortunately, this device contains one operation, using which you should guess the cipher. You can give the device an array of non-negative integers d1,d2,,dn. On the device, there are n lamps, the ith of which is connected to the ith vertex of the tree. For all i, the ith lamp's light will turn on if there exists a vertex of the tree numbered ji where dist(i,j)dj. Let's define dist(i,j) as the distance between vertices i and j in tree, or the number of edges on the simple path between i and j.

Vasya wants to solve this quiz and guess the tree using K operations with the device. Help him!

Interaction

You should implement the following procedure:

vector<int> find_tree(int n, int t)

  • n: Number of vertices in the tree.
  • t: Number of current subtask.
  • t: This procedure is called exactly once, and should return a vector V of 2n2 integers. For integers 0i<n1, V[2i] and V[2i+1] should denote an edge between vertices V[2i] and V[2i+1]. These edges should form a tree, which is equal to the hidden tree.

The above procedure can make calls to the following procedure:

vector<int> device_operation(vector<int> d)

  • d: A vector of n integers between 0 and n1, denoting an operation on the device.
  • t: This procedure returns an array of n integers, where the ith integer is 1 if the lamp of the ith vertex is on, and 0 otherwise.
  • t: This procedure can be called at most 1000 times.

It is guaranteed that in each test the tree is fixed beforehand and won't change depending on your program's operations.

Limits

n=1000.
Let k be the largest number of operations used, among all testcases within the respective subtask.
In subtask 1, you will receive the full 15 points if kK.
In subtask 2, you will receive the full 85 points if kK. If K<k1000, you will receive 85Kk points.
Subtask # Score Constraints
1 15 K=1000
2 85 K=80

Samples

Sample Input 1 Sample Output 1
5 2
00000
11011
11100
10010
? 0 0 0 0 0
? 1 1 2 0 2
? 0 0 0 1 0
? 0 1 0 0 1
!
4 2
1 5
3 4
4 1

In this input example, the tree encrypting the device is:

The table of pairwise distances between the vertices of the tree is:

  • If you make an operation d=[0,0,0,0,0], no lamp will switch on, because dist(i,j)>0 for all ij.
  • If you make an operation d=[1,1,2,0,2], all lamps except the lamp of the 3rd vertex will switch on. For example, the lamp of the 1st vertex will switch on, because dist(1,5)=12=d5.
  • If you make an operation d=[0,0,0,1,0], all lamps except the lamps of the 4th and 5th vertices will switch on.
  • If you make an operation d=[0,1,0,0,1], only the lamps of the 1st and 4th vertices will switch on.



Submitting to 'strangedevice2'


You're not logged in! Click here to login


Submitting to 'strangedevice2'


You're not logged in! Click here to login


Submitting .cpp to 'strangedevice2'


You're not logged in! Click here to login

Time Limit: 4 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Codeforces 1158E

Subtask Score
1 15
2 85
3 0