Дана перестановка, которая состоит из n (n — степень двойки) чисел. Порядок элементов в перестановке вам неизвестен.
Перестановка — это последовательность длины n целых чисел от 1 до n, в которой все числа встречаются ровно по одному разу. Например, [1], [4,3,5,1,2], [3,2,1] — перестановки, а [1,1], [4,3,1], [2,3,4] — нет.
Также имеется следующий запрос: Вы даете массив a длины n, такой что 1≤ai≤n (заметьте, что a не обязательно является перестановкой). В ответ Вы получаете массив c длины n, который генерируется следующим образом:
Вам следует найти заданную перестановку p. Максимальное количество запросов смотрите в параграфе «Оценивание».
Первая строка содержит два целых числа t и q (1≤t,q≤256) — количество наборов входных данных и максимальное количество запросов, которые можно использовать в каждом наборе входных данных.
Для каждого набора входных данных сначала следует прочитать целое число n (1≤n≤1024) — количество элементов в перестановке p.
Гарантируется, что n является степенью двойки (то есть такое целое неотрицательное число k, что 2k=n).
Для совершения запроса выведите «1 a1 a2 ...an» (1≤ai≤n).
В ответ на запрос программа жюри выведет массив c, полученный по правилу из условия, в следующем формате: «c1 c2 ...cn».
После вывода запроса не забудьте вывести символ новой строки и сбросить буфер вывода. В противном случае вы получите вердикт Исчерпан лимит времени
. Для сброса буфера используйте:
fflush(stdout)
или cout.flush()
в C++;
System.out.flush()
в Java;
flush(output)
в Pascal;
stdout.flush()
в Python;
смотрите документацию для других языков.
Обратите внимание, что если ваш запрос недействителен (лимит запросов превышен или входной массив не устраивает ограничением), интерактор выведет «-1» и прекратит работу. Если вы считаете «-1», то немедленно завершите программу, чтобы получить вердикт Неверный ответ
вместо произвольного вердикта.
Когда вы найдете перестановку p, выведите «2 p1 p2 ...pn».
После этого, если это был последний набор входных данных, Вы должны завершить работу своей программы, в противном случае Вы должны продолжить работу по следующим набором входных данных.
1 256 4 0 1 1 1
1 3 2 4 2 2 1 4 2 3
Из первого запроса узнали что p1<p3<p4<p2.
Таким образом искомая перестановка имеет вид: [1,4,2,3].
q — максимальное количество запросов, которое может использовать Ваша программа.
(3 балла) n≤16,q=256,t=128
(7 баллов) n≤32,q=256,t=128
(8 баллов) n≤256,q=256,t=128
(14 баллов) n≤512,q=256,t=128
(20 баллов) n≤512,q=128,t=256
(до 48 баллов) n≤1024,q=127,t=256; Пусть k — максимальное количество запросов, которое Вы использовали в одном наборе данных. Тогда результат за этот тест будет равен:
0 баллов, если k>127;
48−⌈3724(k−55)⌉ баллов, если 55<k≤127;
48 баллов, если k≤55;