Дана перестановка, которая состоит из ( — степень двойки) чисел. Порядок элементов в перестановке вам неизвестен.
Перестановка — это последовательность длины целых чисел от до , в которой все числа встречаются ровно по одному разу. Например, , , — перестановки, а , , — нет.
Также имеется следующий запрос: Вы даете массив длины , такой что (заметьте, что не обязательно является перестановкой). В ответ Вы получаете массив длины , который генерируется следующим образом:
Вам следует найти заданную перестановку . Максимальное количество запросов смотрите в параграфе «Оценивание».
Первая строка содержит два целых числа и () — количество наборов входных данных и максимальное количество запросов, которые можно использовать в каждом наборе входных данных.
Для каждого набора входных данных сначала следует прочитать целое число () — количество элементов в перестановке .
Гарантируется, что является степенью двойки (то есть такое целое неотрицательное число , что ).
Для совершения запроса выведите «1 ...» ().
В ответ на запрос программа жюри выведет массив , полученный по правилу из условия, в следующем формате: « ...».
После вывода запроса не забудьте вывести символ новой строки и сбросить буфер вывода. В противном случае вы получите вердикт Исчерпан лимит времени
. Для сброса буфера используйте:
fflush(stdout)
или cout.flush()
в C++;
System.out.flush()
в Java;
flush(output)
в Pascal;
stdout.flush()
в Python;
смотрите документацию для других языков.
Обратите внимание, что если ваш запрос недействителен (лимит запросов превышен или входной массив не устраивает ограничением), интерактор выведет «-1» и прекратит работу. Если вы считаете «-1», то немедленно завершите программу, чтобы получить вердикт Неверный ответ
вместо произвольного вердикта.
Когда вы найдете перестановку , выведите «2 ...».
После этого, если это был последний набор входных данных, Вы должны завершить работу своей программы, в противном случае Вы должны продолжить работу по следующим набором входных данных.
1 256 4 0 1 1 1
1 3 2 4 2 2 1 4 2 3
Из первого запроса узнали что .
Таким образом искомая перестановка имеет вид: .
— максимальное количество запросов, которое может использовать Ваша программа.
( балла)
( баллов)
( баллов)
( баллов)
( баллов)
(до баллов) ; Пусть — максимальное количество запросов, которое Вы использовали в одном наборе данных. Тогда результат за этот тест будет равен:
баллов, если ;
баллов, если ;
баллов, если ;