Айдос придумал новую головоломку для Темирулана. Он загадал последовательность a из n неотрицательных целых чисел, пронумерованных от 1 до n: a1;a2;…;an.
Темирулан может задавать один из двух типов вопросов:
- ask — Узнать i-е число в загаданной последовательности.
- get_pairwise_xor — Для заданной последовательности различных чисел: i1;i2;…;ik, узнать множество попарных значений xor для элементов последовательности a в индексах i1;i2;…;ik, {aix⊕aiy∣1⩽x,y⩽k}.
Например, если Айдос загадал последовательность [1;5;6;3]. Тогда на вопрос ask(2) Айдос ответит числом 5, а на вопрос get_pairwise_xor({3;4}) Айдос ответит последовательностью [0;0;5;5], так как:
- a3⊕a4=6⊕3=5
- a4⊕a3=3⊕6=5
- a3⊕a3=6⊕6=0
- a4⊕a4=3⊕3=0
Темирулан не справился с этой головоломкой и вам требуется помочь Темирулану. Отгадайте последовательность Айдоса, используя вышеописанные вопросы.
Протокол взаимодействия:
Вам надо реализовать одну функцию: int[] guess(int n)
- n: длина загаданной последовательности.
- Функция вызывается ровно один раз для каждого теста.
- Функция должна вернуть загаданную последовательность в том же порядке.
Ваша программа может вызывать следующие функции:
1. int ask(int i)
- i: индекс в загаданной последовательности, 1⩽i⩽n.
- Функция возвращает i-й элемент в загаданной последовательности.
2. int[] get_pairwise_xor(int[] pos)
- pos: непустой список индексов последовательности.
- Все элементы pos должны быть различными целыми числами.
- Пусть k это количество элементов в pos. Тогда 1⩽posi⩽n для всех 1⩽i⩽k.
- Функция возвращает отсортированный список из k2 элементов: множество попарных значений xor, {aposx⊕aposy∣1⩽x,y⩽k}.
Суммарно вы можете вызывать обе функции не более 200 раз для каждого теста.
Система оценки:
- 2⩽n⩽100
- 0⩽ai⩽109, для всех 1⩽i⩽n.
1. (6 баллов) n⩽4
2. (94 балла) Без дополнительных ограничений. Пусть суммарное количество вызовов функции ask и get_pairwise_xor равно q.
- Если q⩽15, ваш результат 94.
- Если 15<q⩽40, ваш результат 84−2(q−16).
- Если 40<q⩽50, ваш результат 35.
- Иначе, ваш результат 0.