Đây là bài tương tác hai tiến trình. Chỉ các ngôn ngữ C++ tương thích chữ ký được hỗ trợ. Không đọc từ đầu vào chuẩn và không ghi ra đầu ra chuẩn.

Có \(n\) loại trái cây mang nhãn đôi một khác nhau từ \(1\) đến \(n\). Đúng một quả là chanh; Takina và Chisato chưa biết nhãn của nó. Takina nhận lần lượt cả \(n\) quả và phải truyền nhãn quả chanh cho Chisato, người không quan sát quá trình này.

Trước khi nhận trái cây, Takina biết mảng hoán vị \(p\): quả thứ \(i\) được đưa tới có nhãn \(p_i\). Takina viết một chuỗi nhị phân \(b\) dài không quá \(5000\) (có thể rỗng). Gọi \(x=|b|\).

Khi nhận từng quả, Takina được biết nó có phải chanh hay không. Nếu không phải chanh, cô có thể quyết định ăn hoặc không ăn ngay lúc đó; quyết định không thể thay đổi. Nếu là chanh, cô không được ăn. Gọi \(y\) là tổng số quả đã ăn.

Cuối cùng Chisato nhận chuỗi \(b\) và danh sách tăng dần nhãn của các quả không bị ăn. Từ đó cô phải xác định nhãn quả chanh. Có \(t\) ván trong mỗi test.

Yêu cầu cài đặt

Bạn phải cài đặt ba hàm sau trong tệp lời giải.

std::string init(int subtask, int n, std::vector<int> p);

• subtask: chỉ số phần chấm của test.
• n: số trái cây.
• p: vector dài \(n+1\), với \(p[0]=0\) và \(p[i]\) là nhãn quả thứ \(i\) được đưa tới.
• Hàm được gọi một lần ở đầu mỗi ván và phải trả về chuỗi nhị phân \(b\) dài từ \(0\) đến \(5000\).

bool receive_fruit(int id, bool is_lemon);

• id: nhãn quả vừa được đưa tới.
• is_lemon: true khi quả đó là chanh.
• Hàm được gọi \(n\) lần trong mỗi ván.
• Trả về true nếu Takina ăn quả, false nếu không. Trả về true khi is_lemon=true sẽ bị Wrong Answer.

int answer(int subtask, int n, std::string b,
           std::vector<int> uneaten);

• b: chuỗi do init trả về.
• uneaten: vector tăng dần dài \(n-y+1\), trong đó uneaten[0]=0, các phần tử sau là nhãn những quả không bị ăn.
• Hàm được gọi một lần cuối mỗi ván và phải trả về nhãn quả chanh.

Trình chấm chạy lời giải hai lượt:

1. Lượt đầu gọi init, rồi gọi receive_fruit theo thứ tự \(p\) trong từng ván. Lời giải được giữ trạng thái giữa các lần gọi.
2. Lượt hai có thể đổi thứ tự các ván và chỉ gọi answer. Ngoài các tham số của answer, chương trình không được truy cập thông tin từ lượt đầu.

Các hàm được gọi nhiều lần, vì vậy phải xử lý đúng trạng thái còn lại từ ván trước.

Giới hạn

\(p\) là hoán vị của \(1,2,\ldots,n\) và mỗi ván có đúng một quả chanh.

Điểm của mỗi test dùng giá trị \(x\) lớn nhất và \(y\) lớn nhất trong tất cả \(t\) ván của test đó.

Chấm điểm

Ví dụ tương tác

Xét một ván minh họa với \(n=4\) (không thỏa giới hạn thật), \(p=[0,3,1,4,2]\) và quả chanh có nhãn \(4\):

Takina ăn các quả nhãn \(3\) và \(2\), nên uneaten=[0,1,4]. Chiến lược xác định đúng nhãn \(4\) với \(x=3,y=2\).

Tệp đính kèm cung cấp lemon.h, lời giải mẫu khung, trình chấm mẫu và hai dữ liệu mẫu để kiểm thử cục bộ. Trình chấm mẫu chỉ chạy một lượt và không đổi thứ tự ván, khác với trình chấm chính thức.