28430번 - Тайное послание 서브태스크다국어투 스텝
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 128 | 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$), которое ваша программа должна зашифровать (в первом запуске) или расшифровать (во втором запуске).
Следующие $2m$ строк содержат описания $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
1 2 2 1 1 5 2 1 4
예제 출력 1
2 2 3
예제 입력 2
2 2 5 2 2 3 2 1 2
예제 출력 2
1 4 1
노트
Обратите внимание, что в примере приведены конкретные варианты вывода в первом запуске и ввода во втором запуске. Если ваша программа выведет другое множество $R$, при втором запуске ввод также будет другой.
Также при втором запуске зашифрованные сообщения передаются программе участника не обязательно в том порядке, в котором они следовали при первом запуске.
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.