{"problem":{"name":"I. Guess the Tree","description":{"content":"Jury has a complete binary tree with n = 2h - 1 vertices. Its vertices are numbered with distinct integers from 1 to n, but you don't know which vertices are connected with which. You can ask a jury'","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10175I"},"statements":[{"statement_type":"Markdown","content":"Jury has a complete binary tree with n = 2h - 1 vertices. Its vertices are numbered with distinct integers from 1 to n, but you don't know which vertices are connected with which.\n\nYou can ask a jury's program, what is the distance between some two vertices. You must restore tree structure with at most 2.5·h·n such queries.\n\nThis is an interactive problem. Your program should communicate with the jury's program, using standard input and output for that.\n\nIn the very beginning your program gets a single integer n (1 ≤ n ≤ 1023, n + 1 is the power of two) — the number of vertices in the tree.\n\nAfter that you can make at most 2.5·h·n queries. To make a query, output character «_?_» and two integers from 1 to n — numbers of vertices x and y you want to know the distance between. As a response a single integer will be given to you — the distance between vertices x and y.\n\nOnce you find out a complete tree structure, output character «_!_», and then n integers pi, where pi is the parent of vertex i or 0 if i is the root of the tree. After this your program must terminate.\n\nPlease note that each your message must end with a line break. Also after outputting each message your program must flush the stream buffer, so that the outputted information could reach jury's program: for instance, this can be done by calling «_fflush(stdout)_» or «_cout.flush()_» in C++, «_System.out.flush()_» in Java, «_Console.Out.Flush()_» in C#, «_flush(output)_» in Pascal, «_sys.stdout.flush()_» in Python.\n\n## Interaction\n\nThis is an interactive problem. Your program should communicate with the jury's program, using standard input and output for that.In the very beginning your program gets a single integer n (1 ≤ n ≤ 1023, n + 1 is the power of two) — the number of vertices in the tree.After that you can make at most 2.5·h·n queries. To make a query, output character «_?_» and two integers from 1 to n — numbers of vertices x and y you want to know the distance between. As a response a single integer will be given to you — the distance between vertices x and y.Once you find out a complete tree structure, output character «_!_», and then n integers pi, where pi is the parent of vertex i or 0 if i is the root of the tree. After this your program must terminate.\n\n[samples]\n\n## Note\n\nPlease note that each your message must end with a line break. Also after outputting each message your program must flush the stream buffer, so that the outputted information could reach jury's program: for instance, this can be done by calling «_fflush(stdout)_» or «_cout.flush()_» in C++, «_System.out.flush()_» in Java, «_Console.Out.Flush()_» in C#, «_flush(output)_» in Pascal, «_sys.stdout.flush()_» in Python.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n = 2^h - 1 $ for some $ h \\in \\mathbb{Z}^+ $, where $ 1 \\leq n \\leq 1023 $.  \nLet $ T = (V, E) $ be a complete binary tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and unknown edge set $ E $.  \nLet $ d(x, y) $ denote the shortest path distance between vertices $ x, y \\in V $ in $ T $.  \n\n**Constraints**  \n1. $ n + 1 $ is a power of two.  \n2. At most $ \\lfloor 2.5 \\cdot h \\cdot n \\rfloor $ distance queries may be made.  \n3. Each query: output `? x y` for $ x, y \\in V $, receive $ d(x, y) \\in \\mathbb{Z}_{\\geq 0} $.  \n\n**Objective**  \nReconstruct the parent array $ p = (p_1, p_2, \\dots, p_n) $, where $ p_i \\in \\{0\\} \\cup V $, such that:  \n- $ p_i = 0 $ if vertex $ i $ is the root,  \n- $ p_i = j $ if vertex $ j $ is the parent of vertex $ i $,  \nand output `! p_1 p_2 ... p_n`.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10175I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}