| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 127 | 8 | 8 | 14.035% |
Это задача с двойным запуском. На каждом тесте ваше решение будет запущено два раза.
На уроке информатики Алеся и Борис изучают криптографию. Ребята решили изобрести свой способ шифрования сообщений.
Алеся выбирает $k$ различных целых чисел от 1ドル$ до $n$ и обозначает получившееся множество как $T$. Алеся хочет передать Борису в качестве сообщения множество $T$ в зашифрованном виде. Для этого по множеству $T$ Алеся построит и передаст Борису другое множество $R,ドル также состоящее из целых чисел от 1ドル$ до $n$.
Ребята не хотят, чтобы после шифрования размер сообщения изменялся, поэтому $R$ также должно содержать ровно $k$ чисел. А ещё они считают, что если $T$ и $R$ будут содержать хотя бы один общий элемент, то их шифрование будет недостаточно надежным. Поэтому не должно существовать числа, которое входит и в $T,ドル и в $R,ドル то есть множества $T$ и $R$ не должны пересекаться. Гарантируется, что $k \le n / 2,ドル поэтому по множеству $T$ всегда возможно построить хотя бы одно множество $R$.
Когда Борис получит зашифрованное сообщение $R,ドル он должен будет его расшифровать и получить исходное сообщение $T$.
Помогите Алесе и Борису придумать и реализовать алгоритмы шифрования и дешифрования. При первом запуске ваша программа будет выступать в роли Алеси, а при втором запуске --- в роли Бориса.
В первой строке входных данных дано одно число $a,ドル равное 1ドル$ или 2ドル$ --- номер запуска вашей программы.
Во второй строке дано одно число $m$ --- количество сообщений (1ドル \le m \le 300,000円$), которое ваша программа должна зашифровать (в первом запуске) или расшифровать (во втором запуске).
Следующие 2ドルm$ строк содержат описания $m$ сообщений, по две строки на сообщение.
В первой строке сообщения записаны два целых числа $n_i$ и $k_i$ (2ドル \le n_i \le 10^9,ドル 1ドル \le k_i \le 300,000円,ドル $k_i \le \frac{n_i}{2}$). Во второй строке сообщения записаны $k_i$ различных целых чисел от 1ドル$ до $n_i$ в возрастающем порядке.
Гарантируется, что сумма всех значений $k_i$ в одном тесте не превосходит 300ドル,000円$.
Если $a=1,ドル то данные числа являются исходным сообщением. Если $a=2,ドル то данные числа являются результатом запуска вашей программы для шифрования какого-либо сообщения при первом запуске вашей программы.
Программа должна вывести $m$ строк, $i$-я строка должна содержать $k_i$ различных целых чисел от 1ドル$ до $n_i$ в возрастающем порядке.
При первом запуске для каждого исходного сообщения $T_i$ программа должна вывести множество $R_i,ドル которое не должно пересекаться с $T_i$.
При втором запуске программа для каждого зашифрованного сообщения $R_i$ должна восстановить исходное сообщение $T_i$.
Чтобы указать дополнительные ограничения на входные данные, обозначим последовательность чисел, которые задают множество $T_i,ドル как $t_1,ドル $t_2,ドル \dots, $t_{k_i}$. Они расположены в порядке возрастания.
Обозначим сумму $n_i$ в одном тесте как $N$.
Обозначим сумму $k_i$ в одном тесте как $K$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | $N \le 5,000円,ドル $k_i=1$ |
| 2 | 11 | $N \le 5,000円,ドル $k_i=2$ |
| 3 | 9 | $N \leq 300,000円,ドル $k_i=\frac{n_i}{2}$ |
| 4 | 7 | $n_i \le 7,ドル $N \leq 5,000円$ |
| 5 | 9 | $t_{j+1} - t_j \geq 2,ドル $t_{k_i} \leq n_i - 1$ |
| 6 | 9 | $t_{k_i} - t_1 \leq \frac{n_i}{2} - 1$ |
| 7 | 10 | $N \leq 5,000円,ドル $t_{k_i} \leq n_i - k_i$ |
| 8 | 12 | $N \leq 100$ |
| 9 | 3 | $N \leq 5,000円$ |
| 10 | 7 | $N \leq 300,000円$ |
| 11 | 7 | $K \leq 5,000円$ |
| 12 | 7 | Без дополнительных ограничений |
1 2 2 1 1 5 2 1 4
2 2 3
2 2 5 2 2 3 2 1 2
1 4 1
Обратите внимание, что в примере приведены конкретные варианты вывода в первом запуске и ввода во втором запуске. Если ваша программа выведет другое множество $R,ドル при втором запуске ввод также будет другой.
Также при втором запуске зашифрованные сообщения передаются программе участника не обязательно в том порядке, в котором они следовали при первом запуске.