Background

The current testdata of this problem is incorrect.

Translated from ROI 2023 D1T2。

This is an interactive problem. Luogu cannot implement interactive communication, so this problem will be judged in the form of function interaction.

Do not submit using the C++14 (GCC 9) language.

Alesya and Boris are studying cryptography in computer class. They decided to invent their own method of encrypting messages—BASE23 (Boris-Alesya Super Encoding 2023).

Alesya chooses $k$ distinct integers from $1$ to $n$ and calls the resulting set $T$.

Alesya wants to send the set $T$ to Boris as an encrypted message. To do this, based on $T$, Alesya will construct another set $R$ and pass it to Boris. This set also consists of integers in the range from $1$ to $n$.

Alesya and Boris do not want the encrypted message size to change (unlike BASE64, where the ciphertext is about $\frac13$ longer than the plaintext), so $R$ must also contain exactly $k$ numbers. Also, they believe that if $T$ and $R$ share at least one common number, the encryption will not be reliable enough. Therefore, there should not exist a number that belongs to both $T$ and $R$, i.e., $T \cap R = \varnothing$。It is guaranteed that $k\le \frac{n}{2}$, so it is always possible to construct at least one set $R$ from $T$.

When Boris receives the encrypted message $R$, he will need to decrypt it and obtain the original message $T$.

Problem Description

Help Alesya and Boris design and implement the encryption and decryption algorithms of BASE23.

In this problem, your program needs to implement the following two functions (you do not need to write the main function):

std::vector<int> Encode(int n, int k, std::vector<int> T){
	// Encryption process
	return R;
}
std::vector<int> Decode(int n, int k, std::vector<int> R){
	// Decryption process
	return T;
}

Your Encode function plays the role of Alesya and encrypts the array. The Decode function plays the role of Boris and recovers the original array by decryption. Both $T$ and $R$ are sorted in increasing order.

At the beginning, the interaction library will call the Encode function you wrote for the test case and check whether the encryption algorithm is valid based on its return value. Then, the interaction library calls Decode and checks whether its return value is the same as the original data. If it is the same, this BASE23 encryption/decryption code is considered correct.

The interaction library will call these two functions multiple times, corresponding to multiple test cases in the original problem. The library will first encrypt all $T$ for each test case, and then decrypt them in a random order. See the “Hint” section for the specific constraints.

Input Format

Function interaction is used; the program does not need to read input.

Output Format

Function interaction is used; the program does not need to produce output.

Hint

The number of times the interaction library calls the two functions (i.e., the number of test cases) does not exceed $300000$. For each test case, $2\le n\le 10^9,1\le k\le300000,k\le\frac n2$. For each test point, $\sum k\le300000$.

In the original problem, the time limit for both encryption and decryption is $1\text{s}$, and the memory limit is $512\text{MB}$. However, because Luogu implements interactive problems in a special way, this problem uses special time and memory limits. (The current limits may not be enough to pass this problem qwq.)

If you get CE for no clear reason in this problem, you can try submitting in another language.

When you get UKE, check your error message. If it contains “timeout”, it is probably a time limit exceeded.

Interaction library implementation:

Translated by ChatGPT 5