Thầy Huang và các học sinh của mình đang chơi một trò chơi.

Trong trò chơi này, có \(N + 1\) học sinh với ID từ \(0, 1, \ldots, N\); học sinh có ID \(0\) là lớp trưởng. Trò chơi gồm \(M\) vòng, được đánh số \(0, 1, \ldots, M - 1\). Ở vòng \(i\), thầy Huang bí mật gọi học sinh \(A[i]\) vào phòng. Các học sinh nhớ mỗi lần mình được gọi, nhưng họ không được thông báo đã có bao nhiêu vòng trôi qua, cũng như không biết những học sinh nào đã vào phòng trước đó.

Trong suốt trò chơi, lớp trưởng được gọi vào phòng tối đa \(L\) lần, còn mỗi học sinh khác được gọi vào phòng tối đa \(2\) lần. Mục tiêu là mỗi học sinh phải xác định đúng xem lớp trưởng có vào phòng trong khoảng thời gian giữa lần thứ nhất và lần thứ hai học sinh đó được gọi hay không.

Để giao tiếp với nhau, các học sinh tập hợp lại và thống nhất một chiến lược chung. Trước tiên, họ sẽ đặt \(K\) tấm thẻ, được đánh số từ \(0\) đến \(K - 1\), trong phòng; mỗi tấm thẻ có một mặt đen và một mặt trắng. Ban đầu, tất cả các thẻ đều được đặt với mặt đen úp lên. Trong mỗi vòng, học sinh bước vào phòng, quan sát màu của các tấm thẻ, và có thể lật tùy ý số thẻ bất kỳ. Đối với mỗi học sinh \(1, 2, \ldots, N\), ngay sau lần ghé thăm thứ hai, họ phải báo cáo ngay liệu lớp trưởng có vào phòng trong khoảng giữa lần ghé thứ nhất và lần ghé thứ hai của học sinh đó hay không.

Nhiệm vụ của bạn là thiết kế một chiến lược cho các học sinh đảm bảo họ trả lời đúng tất cả các câu hỏi. Điểm số của lời giải phụ thuộc vào giá trị của \(K\) (xem phần Chấm điểm để biết chi tiết).

Chi tiết cài đặt

Bạn cần cài đặt bốn hàm sau trong file game.h:

int start_game(int L, int N, int i)

• \(L\): số lần tối đa lớp trưởng được gọi vào phòng.
• \(N\): số học sinh, không tính lớp trưởng.
• \(i\): ID của học sinh.
• Hàm này trả về số \(K\).
• Giá trị \(K\) phải giống nhau với cùng tham số \(L\) và \(N\), bất kể \(i\).
• Giá trị \(K\) phải nằm trong đoạn \([0, 64]\).
• Hàm này được gọi tối đa \(500\) lần cho mỗi test case.

std::vector<bool> leader(std::vector<bool> c)
std::vector<bool> student_first(std::vector<bool> c)
std::pair<bool, std::vector<bool>> student_second(std::vector<bool> c)

• Hàm leader cài đặt chiến lược của lớp trưởng.
• Hàm student_first cài đặt chiến lược của các học sinh khác cho lần ghé thăm phòng đầu tiên.
• Hàm student_second cài đặt chiến lược của các học sinh khác cho lần ghé thăm phòng thứ hai.
• c: mảng có độ dài \(K\). Mặt trắng của thẻ thứ \(i\) đang úp lên khi và chỉ khi c[i] = true lúc học sinh bước vào phòng.
• Các mảng boolean được trả về bởi các hàm phải có độ dài \(K\). Phần tử thứ \(i\) bằng true khi và chỉ khi mặt trắng của thẻ thứ \(i\) đang úp lên sau khi học sinh rời phòng.
• Phần tử đầu tiên của cặp trả về bởi student_second là câu trả lời: lớp trưởng có vào phòng trong khoảng giữa lần thứ nhất và lần thứ hai của học sinh đó hay không.
• Tổng cộng, cả ba hàm được gọi tối đa \(5000\) lần cho mỗi test case.

Trong quá trình chấm, mỗi tiến trình đại diện cho một học sinh. Mỗi tiến trình sẽ theo một trong ba kịch bản sau:

• Tiến trình chỉ nhận đúng một lần gọi start_game với \(i = 0\) và sau đó là các lần gọi leader, tối đa \(L\) lần.
• Trong trường hợp này, leader được gọi cho vòng \(r\) khi và chỉ khi: \(A[r] = 0\), leader đã được gọi đúng một lần cho mỗi vòng \(r' < r\) với \(A[r'] = 0\), và chưa có lần gọi leader nào cho vòng \(r' > r\).
• Tiến trình chỉ nhận đúng một lần gọi start_game với \(i \neq 0\), tối đa một lần gọi student_first, và tối đa một lần gọi student_second, theo thứ tự đó.
• Nếu student_first được gọi cho vòng \(r\), thì \(A[r]\) là lần xuất hiện đầu tiên của \(i\) trong mảng.
• Nếu student_second được gọi cho vòng \(r\), thì \(A[r]\) là lần xuất hiện thứ hai của \(i\) trong mảng, và student_first phải đã được gọi trước.
• Tiến trình không nhận bất kỳ lần gọi nào tới bốn hàm trên.

Nói cách khác, bất kỳ tiến trình nào nhận lần gọi start_game sẽ được gọi cho mọi vòng \(r\) trong một tiền tố của các vòng mà \(A[r] = i\), và không có lần gọi nào khác sẽ được thực hiện.

Ngoài các ràng buộc trên, chương trình của bạn phải tất định (deterministic), tức là phải hoạt động như nhau với cùng chuỗi lần gọi và cùng tham số. Hành vi của chương trình chỉ được và phải chỉ được quyết định bởi tất cả các lần gọi start_game, leader, student_first và student_second. Đặc biệt, mỗi tiến trình sẽ có các biến toàn cục riêng được khởi tạo bình thường.

Hơn nữa, trong mỗi test case, chương trình sẽ được khởi động lại tối đa \(500\) lần. Lưu ý rằng dữ liệu toàn cục khởi tạo khác không quá lớn sẽ có thể gây "Execution timed out" trong trường hợp này.

Ràng buộc

• \(1 \le L \le 4095\)
• \(1 \le N \le 128\)
• \(1 \le M \le L + 2N\)
• Bộ chấm là adaptive (thích nghi); giá trị \(M\) và mảng \(A\) có thể thay đổi trong quá trình chấm miễn là nhất quán với các lần gọi trước.

Phân nhóm

• Subtask 1 (6 điểm): \(L = 1\).
• Subtask 2 (14 điểm): \(N \le 64\).
• Subtask 3 (80 điểm): Không có ràng buộc thêm.

Ví dụ

Xét tình huống với \(L = 4\), \(N = 2\), \(M = 8\), \(A = [1, 0, 2, 0, 2, 0, 1, 0]\).

Bộ chấm tạo ra ba tiến trình A, B và C. Tiến trình A đại diện cho lớp trưởng (học sinh \(0\)), tiến trình B đại diện cho học sinh \(1\), và tiến trình C đại diện cho học sinh \(2\).

Trước khi trò chơi bắt đầu, giả sử chiến lược của các học sinh như sau:

• Họ cần hai tấm thẻ (\(K = 2\)).
• Lớp trưởng luôn lật cả hai thẻ mỗi khi được gọi vào phòng.
• Trong lần ghé thăm đầu tiên của các học sinh khác, họ lật tấm thẻ tương ứng của mình (thẻ \(0\) cho học sinh \(1\), thẻ \(1\) cho học sinh \(2\)), và ghi nhớ màu của mặt đang úp lên.
• Trong lần ghé thăm thứ hai, nếu tấm thẻ được giao đã bị lật sang mặt khác, họ suy ra rằng lớp trưởng đã vào phòng trong khoảng giữa hai lần ghé của mình.

Đầu tiên, ba lần gọi sau được thực hiện:

Theo chiến lược, cả ba lần gọi đều trả về \(K = 2\).

Vòng \(0\): \(A[0] = 1\). Lần gọi sau được thực hiện trên tiến trình B cho học sinh \(1\):

student_first([0, 0]);

Học sinh biết mình là học sinh \(1\) từ lần gọi trước start_game(2, 2, 1). Theo chiến lược, học sinh lật thẻ \(0\). Do đó hàm trả về [1, 0].

Vòng \(1\): \(A[1] = 0\). Lần gọi sau được thực hiện cho học sinh \(0\) trên tiến trình A:

leader([1, 0]);

Theo chiến lược, lớp trưởng lật cả hai thẻ, trả về [0, 1].

Tiếp theo, các lần gọi sau được thực hiện:

Vòng \(4\): học sinh \(2\) được gọi vào phòng lần thứ hai. Lần gọi sau được thực hiện trên tiến trình C:

student_second([1, 1]);

Học sinh \(2\) biết rằng thẻ \(1\) đang úp mặt đen lên trong lần ghé trước của mình, nhưng bây giờ đang úp mặt trắng lên. Do đó lớp trưởng chắc chắn đã vào phòng trong khoảng giữa hai lần ghé. Hàm trả về (true, [1, 1]).

Cuối cùng, các vòng còn lại diễn ra như sau:

Tất cả học sinh đều trả lời đúng. Do đó test case được coi là chính xác.

Giải thích ví dụ: Học sinh \(2\) đã ghé phòng lần đầu ở vòng \(2\), lúc đó thẻ \(1\) đang úp mặt đen (\(c[1] = 0\)), và học sinh lật thẻ này thành mặt trắng rồi về. Lớp trưởng vào phòng ở vòng \(3\) và lật cả hai thẻ, khiến thẻ \(1\) quay về mặt đen. Nhưng lớp trưởng lại vào thêm ở vòng \(4\) không — thực ra vòng \(4\) chính là học sinh \(2\) ghé lần hai, và thẻ \(1\) đang mặt trắng do lớp trưởng đã lật lại ở vòng \(3\). Chờ — thực tế: sau vòng \(3\) (lớp trưởng) thẻ trạng thái là [1,1]. Học sinh \(2\) thấy [1,1] ở vòng \(4\), trong khi lúc lần ghé đầu (vòng \(2\)) học sinh thấy [0,1] và để lại [0,0]. Vì thẻ \(1\) đã thay đổi từ \(0\) (mặt đen) thành \(1\) (mặt trắng), học sinh kết luận lớp trưởng đã vào phòng — câu trả lời là có.

Chấm điểm

Trong bất kỳ test case nào, nếu ít nhất một trong các điều kiện sau xảy ra, điểm số của lời giải cho test case đó sẽ là \(0\) (báo cáo là Output isn't correct trên CMS):

• Ít nhất một trong các mảng trả về có độ dài khác \(K\).
• Phần tử đầu tiên của cặp trả về bởi student_second là sai.
• Giá trị trả về không nhất quán với cùng chuỗi lần gọi và cùng tham số (tức là chương trình không tất định).

Ngược lại, ở subtask 1 và 2, bạn sẽ nhận điểm tối đa. Ở subtask 3, điểm được tính như sau: