Ilshat là kỹ sư phần mềm nghiên cứu các cấu trúc dữ liệu hiệu quả. Anh thiết kế một cấu trúc dữ liệu lưu một tập các số nguyên không âm \(n\) bit, trong đó \(n=2^b\) với một số nguyên không âm \(b\).

Ban đầu tập rỗng. Chương trình sử dụng cấu trúc dữ liệu phải tuân theo trình tự:

1. Thêm các số nguyên \(n\) bit vào tập bằng add_element(x), mỗi lần một số. Thêm lại một phần tử đã có không làm thay đổi tập.
2. Sau khi thêm phần tử cuối cùng, gọi compile_set() đúng một lần.
3. Sau đó, có thể gọi check_element(x) nhiều lần để kiểm tra phần tử \(x\) có thuộc tập hay không.

Ilshat đã mắc lỗi trong compile_set(): hàm sắp xếp lại các bit của mọi phần tử theo cùng một hoán vị chưa biết. Bạn cần xác định hoán vị đó.

Gọi \(p=[p_0,\ldots,p_{n-1}]\) là một hoán vị của các số từ \(0\) đến \(n-1\). Một phần tử có biểu diễn nhị phân \(a_0,\ldots,a_{n-1}\), với \(a_0\) là bit có trọng số lớn nhất, sẽ bị thay bằng phần tử có các bit

Cùng một hoán vị \(p\) được dùng cho mọi phần tử. Hoán vị có thể bất kỳ, kể cả hoán vị đồng nhất \(p_i=i\) với mọi \(i\). Trình chấm cố định \(p\) trước khi gọi hàm của bạn.

Ví dụ, với \(n=4\), \(p=[2,1,3,0]\), nếu tập chứa 0000, 1100, 0111, thì sau compile_set() tập sẽ chứa 0000, 0101, 1110.

Bạn cần chọn các phần tử để thêm vào tập, gọi compile_set() đúng một lần, kiểm tra một số phần tử trong tập đã biến đổi, rồi dùng thông tin thu được để xác định và trả về \(p\). Có thể gọi add_element nhiều nhất \(w\) lần và check_element nhiều nhất \(r\) lần. Việc thêm một phần tử đã có vẫn được tính là một lần gọi.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong messy.h:

std::vector<int> restore_permutation(int n, int w, int r);

Trong Java, cài đặt phương thức sau trong lớp messy:

public int[] restore_permutation(int n, int w, int r)

Trong C, giao diện là:

void restore_permutation(int n, int w, int r, int* result);

• n: số bit của mỗi phần tử, đồng thời là độ dài hoán vị.
• w: số lần tối đa được gọi add_element.
• r: số lần tối đa được gọi check_element.
• Với C++ và Java, trả về mảng độ dài \(n\) chứa đúng hoán vị \(p\) theo thứ tự \(p_0,\ldots,p_{n-1}\).
• Với C, ghi \(p_i\) vào result[i] của mảng đã được cấp sẵn, với mọi \(0 \le i < n\).

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "messy.h" thay cho #include "messy_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Các hàm thư viện

Thư viện C++ cung cấp các hàm sau trong messy.h:

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

Thư viện C cung cấp:

void add_element(char* x);
int check_element(char* x);
void compile_set();

Trong Java, gọi các phương thức tĩnh của lớp grader:

public static void add_element(String x)
public static boolean check_element(String x)
public static void compile_set()

• add_element(x): thêm phần tử có biểu diễn nhị phân x vào tập. Chỉ được gọi trước compile_set().
• compile_set(): áp dụng phép hoán vị bit cho toàn bộ tập. Phải gọi đúng một lần. Không được thêm phần tử sau lời gọi này, và không được kiểm tra phần tử trước lời gọi này.
• check_element(x): trả về true nếu phần tử được biểu diễn bởi x thuộc tập sau khi biến đổi, và false nếu không. Trong C, các giá trị tương ứng là \(1\) và \(0\).

Mỗi xâu x truyền cho add_element hoặc check_element phải có đúng \(n\) ký tự, chỉ gồm 0 và 1. Ký tự đầu tiên biểu diễn bit có trọng số lớn nhất. Vi phạm giới hạn số lời gọi, thứ tự thao tác hoặc định dạng xâu sẽ bị chấm Wrong Answer.

Ràng buộc

• \(n\) là lũy thừa của \(2\); các giá trị cụ thể của \(n,w,r\) được cho trong bảng subtasks.
• \(p\) là hoán vị của \(0,1,\ldots,n-1\), được cố định trước lời gọi restore_permutation.
• compile_set() phải được gọi đúng một lần, kể cả khi đã suy ra hoán vị.

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm.

Ví dụ

Trình chấm gọi:

restore_permutation(4, 16, 16)

Chương trình được thêm phần tử nhiều nhất \(16\) lần và kiểm tra nhiều nhất \(16\) lần. Một chuỗi thao tác có thể là:

add_element("0001")
add_element("0011")
add_element("0100")
compile_set()
check_element("0001") -> false
check_element("0010") -> true
check_element("0100") -> true
check_element("1000") -> false
check_element("0011") -> false
check_element("0101") -> false
check_element("1001") -> false
check_element("0110") -> false
check_element("1010") -> true
check_element("1100") -> false

Chỉ có một hoán vị phù hợp với các kết quả kiểm tra này: \(p=[2,1,3,0]\). Vì vậy, restore_permutation phải trả về [2, 1, 3, 0].

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n,w,r\) và dòng tiếp theo chứa \(n\) số \(p_0,\ldots,p_{n-1}\). Các số này mô tả hoán vị dùng để mô phỏng thư viện; hàm của bạn nhận \(n,w,r\) và sử dụng các lời gọi thư viện để tìm hoán vị.

Nếu hàm trả về mảng độ dài \(n\), trình chấm mẫu C++ in các phần tử của mảng đó trên một dòng. Nếu trả về sai độ dài hoặc vi phạm quy tắc gọi thư viện, trình chấm mẫu in WA. Trình chấm mẫu C++ không tự so sánh từng phần tử của mảng trả về với \(p\); bạn cần kiểm tra kết quả khi thử chương trình.

4 16 16
2 1 3 0

2 1 3 0

Nguồn

IOI 2016, ngày thi thứ hai, bài Unscrambling a Messy Bug. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.