Codeforces Round 385 (Div. 1) |
---|
Закончено |
Это интерактивная задача. В секции «Протокол взаимодействия» вы найдёте информацию о том, как сбрасывать буфер вывода (делать операцию 'flush').
В этой задаче вам предстоит играть в игру с самим Коровоконгом, какое везение!
Коровоконг загадал некоторую матрицу M размера n на n. Обозначим через Mi, j элемент, расположенный в i-й строке и j-м столбце данной матрицы. Строки и столбцы нумеруются от 1 до n.
Элементы матрицы являются целыми числами от 0 до 109. Кроме того, гарантируется, что Mi, i = 0 для всех i от 1 до n. Ваша задача — вычислить минимальный элемент в каждой строке без учёта диагонального элемента. Формально, для каждого i требуется найти .
Разумеется, чтобы это сделать, вам придётся задавать Коровоконгу вопросы.
Каждый вопрос Коровоконгу является множеством индексов {w1, w2, ..., wk} для некоторого k от 1 до n. Коровоконг отвечает n числами, i-е из которых является минимумом в i-й строке по заданным позициям, то есть min1 ≤ j ≤ kMi, wj.
Коровоконг считает, что вам вполне хватит 20 вопросов, чтобы отгадать все требуемые значения.
Для того чтобы вывести ответ, требуется сначала напечатать - 1 в отдельной строке, после чего вывести n чисел ответа в следующей строке. i-е из этих чисел должно быть минимумом в i-й строке, если не учитывать i-й элемент. Не забывайте делать операцию 'flush' после вывода ответа. Вывод ответа не считается запросом.
Вы получите вердикт Wrong Answer если:
Вы получите вердикт Idleness Limit Exceeded, если не будете ничего выводить (а тестирующая программа будет ожидать ввода) или забудете сделать операцию 'flush' после какого-нибудь вывода (смотри ниже).
В первой строке входных данных записано целое число n (2 ≤ n ≤ 1, 000).
Чтобы вывести ответ, выведите сначала -1 в отдельной строке. Далее выведите n целых чисел, i-е из которых должно равняться минимальному числу в i-й строке без учёта диагональных элементов. Не забывайте делать операцию 'flush'!.
Чтобы задать вопрос Коровоконгу, выведите сначала целое число k в отдельной строке — размер множества индексов. В следующей строке выведите k целых чисел w1, w2, ... wk. Не забудьте сделать операцию 'flush', чтобы получить ответ.
Ответ Коровоконга будет строкой, содержащей n целых чисел, i-е из которых будет равно минимальному значению Mi, wj по всем j от 1 до k.
Вы можете задать не более 20 вопросов, в противном случае вы получите вердикт Wrong Answer.
Для сброса буфера вывода (то есть для операции 'flush') сразу после вывода числа или ответа и перевода строки можно сделать:
Hacking Для взломов следуйте следующему формату:
n
M_{1,1} M_{1,2} ... M_{1,n}
M_{2,1} M_{2,2} ... M_{2,n}
...
M_{n,1} M_{n,2} ... M_{n,n}
Разумеется, взламываемому решению не будет доступен данный ввод.
3
0 0 0
2 7 0
0 0 4
3 0 8
0 5 4
3
1 2 3
1
3
2
1 2
1
2
1
1
-1
2 5 4
2
0 0
0 0
1
2
1
1
-1
0 0
В первом примере Коровоконг загадал следующую матрицу:
[
[0, 3, 2],
[5, 0, 7],
[4, 8 ,0],
]
Далее приведён протокол взаимодействия в более наглядном формате. Левый столбец соответствует ответам Коровоконга, а правый — возможным запросам участника.
3
3
1 2 3
0 0 0
1
3
2 7 0
2
1 2
0 0 4
1
2
3 0 8
1
1
0 5 4
-1
2 5 4
Второй пример показывает, что и недиагональные элементы могут быть равны нулю.
Название |
---|