Жюри задумало полное бинарное дерево с n = 2h - 1 вершинами. Его вершины пронумерованы целыми различными числами от 1 до n, однако вам неизвестно, какие вершины с какими соединены.
Вы можете спрашивать у программы жюри, чему равно расстояние между некоторыми двумя вершинами. Вы должны с помощью не более чем 2.5·h·n таких запросов восстановить структуру дерева.
Это интерактивная задача. Ваша программа должна общаться с программой жюри, используя для этого стандартные потоки ввода и вывода.
В самом начале вашей программе сообщается единственное число n (1 ≤ n ≤ 1023, n + 1 — степень двойки) — количество вершин в дереве.
После этого вы можете сделать не более 2.5·h·n запросов. Чтобы сделать запрос, выведите символ «?» и два целых числа от 1 до n — номера вершин x и y, расстояние между которыми вы хотите узнать. В ответ на такой запрос вам будет сообщено одно целое число — расстояние между вершинами x и y.
Как только вы узнаете полную структуру дерева, выведите символ «!», а затем n целых чисел pi, где pi — это предок вершины i, либо число 0, если вершина i является корнем дерева. После этого ваша программа должна завершиться.
<interactor's output>
? 1 2
<interactor's output>
? 2 3
<interactor's output>
! 2 0 2
3
<solution's output>
1
<solution's output>
1
<solution's output>
Обратите внимание, что каждое выведенное вами сообщение должно завершаться переводом строки. Также после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы «fflush(stdout)» или «cout.flush()» в C++, «System.out.flush()» в Java, «Console.Out.Flush()» в C#, «flush(output)» в Pascal, «sys.stdout.flush()» в Python.
Название |
---|