Cửa hàng JOI bán \(N\) món hàng, đánh số từ \(0\) đến \(N-1\). Giá của món hàng \(i\) là \(P_i\). Hai món hàng bất kỳ có giá khác nhau.

Anna đến mua sắm. Trong các món có chỉ số từ \(L\) đến \(R\), kể cả hai đầu mút, cô muốn mua món rẻ nhất. Anna không biết giá từng món nên sẽ trao đổi với Bruno, nhân viên cửa hàng, để quyết định mua món nào. Bruno biết giá mọi món nhưng không biết \(L,R\).

Anna và Bruno dùng thiết bị viễn thông để gửi các ký tự \(0\) hoặc \(1\). Anna được gửi tối đa \(18\) ký tự cho Bruno; Bruno được gửi tối đa \(10000\) ký tự cho Anna. Bruno muốn gửi càng ít ký tự càng tốt.

Anna được cho \(N,L,R\); Bruno được cho \(N\) và giá mọi món hàng. Hãy viết các chương trình thực hiện chiến lược của Anna và Bruno để Anna xác định chỉ số món hàng cần mua.

Chi tiết cài đặt

Bạn cần nộp hai tệp.

Tệp Anna.cpp cài đặt chiến lược của Anna, nạp Anna.h bằng chỉ thị #include và cài đặt các hàm:

void InitA(int N, int L, int R);
void ReceiveA(bool x);
int Answer();

• InitA được gọi đúng một lần lúc bắt đầu mỗi bộ dữ liệu. N là số món hàng, L,R xác định đoạn chỉ số mà Anna muốn tìm món rẻ nhất.
• ReceiveA được gọi mỗi khi Bruno gửi một ký tự cho Anna. x là ký tự đó: true biểu diễn \(1\), false biểu diễn \(0\).
• Answer được gọi đúng một lần khi mọi lời gọi trao đổi đã kết thúc. Hàm trả về chỉ số món hàng Anna sẽ mua. Giá trị phải nằm trong đoạn \([L,R]\); nếu không, chương trình bị chấm Wrong Answer [1]. Nếu chỉ số không phải món hàng rẻ nhất cần mua, chương trình bị chấm Wrong Answer [2].

Trong tệp này, bạn có thể gọi hàm sau để Anna gửi một ký tự cho Bruno:

void SendA(bool y);

Tham số y là ký tự gửi đi, với true là \(1\) và false là \(0\).

Tệp Bruno.cpp cài đặt chiến lược của Bruno, nạp Bruno.h bằng chỉ thị #include và cài đặt:

void InitB(int N, std::vector<int> P);
void ReceiveB(bool y);

• InitB được gọi đúng một lần lúc bắt đầu mỗi bộ dữ liệu. N là số món hàng; P là mảng độ dài \(N\), trong đó P[i] là giá món hàng \(i\).
• ReceiveB được gọi mỗi khi Anna gửi một ký tự cho Bruno. y là ký tự đó: true là \(1\), false là \(0\).

Trong tệp này, bạn có thể gọi hàm sau để Bruno gửi một ký tự cho Anna:

void SendB(bool x);

Tham số x là ký tự gửi đi, với true là \(1\) và false là \(0\).

Thứ tự thực hiện

Với mỗi bộ dữ liệu, có hai hàng đợi: \(Q_Y\) chứa các ký tự Anna gửi và \(Q_X\) chứa các ký tự Bruno gửi. Đầu tiên, InitA và InitB được gọi; các ký tự được gửi trong hai hàm này được thêm vào hàng đợi tương ứng. Sau đó, lặp lại quy trình:

• Nếu ít nhất một hàng đợi không rỗng, lấy ký tự ở đầu một hàng đợi không rỗng và gọi ReceiveA hoặc ReceiveB tương ứng. Nếu cả hai đều không rỗng thì không xác định trước hàm nào trong hai hàm sẽ được gọi.
• Khi SendA được gọi trong lúc thực hiện ReceiveA, ký tự gửi đi được thêm vào \(Q_Y\).
• Khi SendB được gọi trong lúc thực hiện ReceiveB, ký tự gửi đi được thêm vào \(Q_X\).
• Khi cả hai hàng đợi đều rỗng, Answer được gọi và chương trình kết thúc.

Anna không được gửi quá \(18\) ký tự; nếu vượt quá thì bị chấm Wrong Answer [3]. Bruno không được gửi quá \(10000\) ký tự; nếu vượt quá thì bị chấm Wrong Answer [4].

Lưu ý quan trọng

• Bạn có thể viết thêm hàm nội bộ hoặc dùng biến toàn cục. Hai tệp nộp được biên dịch cùng grader thành một tệp thực thi. Mọi hàm nội bộ và biến toàn cục cần nằm trong namespace không tên để tránh xung đột với tệp khác. Khi chấm thực tế, Anna và Bruno chạy trong hai tiến trình và không thể chia sẻ biến toàn cục.
• Chương trình không được dùng đầu vào chuẩn, đầu ra chuẩn hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Biên dịch và chạy thử

Trang cuộc thi cung cấp gói gồm grader mẫu và các tệp chương trình mẫu. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng thư mục, rồi biên dịch:

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp

Nếu thành công, tệp thực thi grader được tạo. Grader thực tế khác grader mẫu. Grader mẫu chỉ chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn và đầu ra lỗi chuẩn.

Dữ liệu vào

Grader mẫu đọc theo định dạng:

N L R
P_0 P_1 ... P_{N-1}

Dữ liệu ra

Khi chương trình kết thúc bình thường, grader mẫu ghi:

• Nếu đáp án đúng: Accepted: Y X, trong đó \(Y\) là tổng số ký tự Anna gửi cho Bruno và \(X\) là tổng số ký tự Bruno gửi cho Anna.
• Nếu bị chấm sai: loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình thỏa mãn nhiều loại lỗi, grader mẫu chỉ thông báo một loại.

Ràng buộc

• \(1\le N\le1000000\).
• \(0\le L\le R\le N-1\).
• \(1\le P_i\le N\) với mọi \(0\le i\le N-1\).
• \(P_i\ne P_j\) với mọi \(0\le i<j\le N-1\).

Phân nhóm

• Nhóm 1 (1 điểm): \(N\le1000\).
• Nhóm 2 (9 điểm): \(N\le10000\).
• Nhóm 3 (90 điểm): Không có ràng buộc bổ sung. Điểm được tính như dưới đây.

Gọi \(T\) là số ký tự lớn nhất mà Bruno gửi cho Anna trên tất cả bộ dữ liệu của nhóm 3.

Ở đây, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

4 0 2
3 1 4 2

Lời gọi hàm

Giải thích

Bảng ghi các lời gọi hàm tương ứng với đầu vào mẫu.

Ví dụ này thỏa mãn các nhóm \(1,2,3\).

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 2. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.