Hidden Colored Graph solution codechef

Hidden Colored Graph solution codechef


There is a hidden undirected graph with nn vertices. There are no self-loops or multiple edges. Each vertex is colored black or white, and the colors are also hidden from you.

To make a query, you choose a vertex vv. The interactor will respond with the current color of vv, and then it will flip the colors of all vertices adjacent to vv. A vertex is not considered adjacent to itself, so the color of vv doesn’t change.

After at most 60006000 queries, find the adjacency matrix of the graph.

Note: The interactor is not adaptive. In other words, the graph and colors are fixed in the beginning.

Interaction

Begin the interaction by reading a single integer nn – the number of vertices in the graph.

To ask a query, output “? v” for a vertex vv (1vn1≤v≤n). Then read a single character describing the current color of vv, where “B” denotes black and “W” denotes white. After making this query, the colors of all vertices adjacent to vv will flip.

To print the answer, output “!” then on the next nn lines print nn strings of length nn, consisting of symbols “0” and “1“. The jj-th character of the ii-th string should be “1” if and only if there is an edge between vertices ii and jj. Since there are no self-loops, the main diagonal should contain only “0“.

If at any time you make an invalid query or exceed the query limit, the interaction is terminated and you will receive a Wrong Answer verdict.

Remember to flush the output after printing each line!

Constraints

  • 1n1001≤n≤100

Sample Input 1 

3

W

B

B

W

Sample Output 1 

? 1

? 2

? 3

? 2

!
001
001
110

Explanation

The example is given to demonstrate how the queries work, and it is not guaranteed that the answer can be uniquely determined from the queries in the example.

The hidden graph is a path 1321−3−2. Initially, the colors for nodes 112233 are white, black, black, respectively. Denote it by the string WBB.

The first query asks for node 11. The interactor responds with its color W then flips the color of node 33. The colors are now WBW.

The second query asks for node 22. The interactor responds with its color B then flips the color of node 33. The colors are now WBB.

The third query asks for node 33. The interactor responds with its color B then flips the colors of nodes 11 and 22. The colors are now BWB.

The fourth query asks for node 22. The interactor responds with its color W then flips the color of node 33. The colors are now BWW.

Then the correct adjacency matrix is guessed.

Leave a Comment