{"problem":{"name":"Near Pair","description":{"content":"This is an **interactive problem**, where your program interacts with the judge system via Standard Input and Output. You are given integers $N$, $K$, and $Q$.   The judge holds a hidden permutation $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_1_i"},"statements":[{"statement_type":"Markdown","content":"This is an **interactive problem**, where your program interacts with the judge system via Standard Input and Output.\nYou are given integers $N$, $K$, and $Q$.  \nThe judge holds a hidden permutation $(a_1, a_2, \\dots, a_N)$ of $(1, 2, \\dots, N)$.  \nYou may ask up to $Q$ queries to the judge, where each query is as follows:\n\n*   Choose a subset $S$ from $\\lbrace 1, 2, \\dots, N \\rbrace$. The judge will return the number of distinct pairs $(i, j)$ such that $i < j$ and $|a_i - a_j| \\leq K$ where $i, j \\in S$.\n\nLet $x$ be the index $t$ where $a_t = 1$, and $y$ be the index $t$ where $a_t = N$. Your task is to identify the set $\\lbrace x, y \\rbrace$. (You do not need to distinguish which is $x$ and which is $y$.)\nThe judge is non-adaptive, that means the permutation $(a_1, a_2, \\dots, a_N)$ is fixed before any interaction begins.\n\n## Constraints\n\n*   All input values are integers.\n*   $N = 20000$\n*   $1 \\leq K \\leq 10$\n*   $Q = 30(K + 1)$\n\n## Input And Output\n\nThis is an interactive problem.\nFirst, read integers $N$, $K$, and $Q$ from the Standard Input:\n\n$N$ $K$ $Q$\n\nThen, repeat the following process until you identify the set $\\lbrace x, y \\rbrace$:\nFor a query, output the following format to the Standard Output:\n\n? $s_1s_2 \\dots s_N$\n\nHere, $s_1 s_2 \\dots s_N$ is a binary string of length $N$ representing the subset $S$, where $s_i = {}$`1` if $i \\in S$, and $s_i = {}$`0` otherwise.\nThe response to your query will be provided in the Standard Input in the following format:\n\n$T$\n\nHere, $T$ is the answer to the query, representing the number of distinct pairs $(i, j)$ such that $i < j$ and $|a_i - a_j| \\leq K$ where $i, j \\in S$.\nOnce you identify the set $\\lbrace x, y \\rbrace$, output the two elements in the following format (order does not matter) and terminate your program immediately:\n\n! $x$ $y$\n\n### Notes\n\n*   **Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.**\n*   If your query format is invalid or you exceed the number of queries, the judge will respond with $T = -1$. If you receive this response, you should immediately terminate your program. Otherwise, you may get a TLE verdict.\n*   Beware that unnecessary newlines are considered as malformed.\n\n## Partial Score\n\n$30$ points will be awarded for passing the test set satisfying the additional constraint $K = 10$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_1_i","tags":[],"sample_group":[],"created_at":"2026-03-03 11:01:14"}}