플래티넘 IVThere are \(n\) switches and \(n\) doors. Each switch is connected to exactly one door (a bijection) and has one correct position (\(0\) or \(1\)) that opens its door. You must determine, for every switch, its correct position and which door it controls.
This is an interactive task. You may ask queries: fix a position for every switch and the grader replies with the smallest-numbered door that is still closed, or \(-1\) if all doors are open. Use at most the allowed number of queries, then output your answer.
Note. This is an adaptation of an IOI function-implementation task to an interactive stdin/stdout problem. The test data is RiseOJ-generated (self-validated against an independent brute force), not the official IOI data.
Interaction / I/O protocol
Input. The grader first sends \(n\) on its own line.
Output. Query: print ? c_0 c_1 ... c_{n-1} (each \(c_i \in \{0,1\}\)) and flush; read back one integer (the first closed door, or \(-1\)).
Answer: print ! S_0 ... S_{n-1} D_0 ... D_{n-1} and flush, where \(S_i\) is switch \(i\)'s correct position and \(D_i\) is the door it controls. Then terminate. You may use at most 40000 queries.
Example. With \(n=4\), correct positions 1 0 1 1 and switch\(\to\)door map 3 0 1 2, a correct interaction ends with ! 1 0 1 1 3 0 1 2.
- \(1 \le n \le 200\)
- Switch\(\to\)door is a bijection; each switch has a unique correct bit.
The grader first sends \(n\) on its own line.
Query: print ? c_0 c_1 ... c_{n-1} (each \(c_i \in \{0,1\}\)) and flush; read back one integer (the first closed door, or \(-1\)).
Answer: print ! S_0 ... S_{n-1} D_0 ... D_{n-1} and flush, where \(S_i\) is switch \(i\)'s correct position and \(D_i\) is the door it controls. Then terminate. You may use at most 40000 queries.