Một trò chơi điện tử mới vừa được phát hành. Trong thế giới của trò chơi có \(N\) quái vật, được đánh số từ \(0\) đến \(N-1\). Mỗi quái vật có một số nguyên gọi là sức mạnh. Sức mạnh của quái vật \(i\) (\(0 \le i \le N-1\)) là \(S_i\). Ta biết rằng:

• Sức mạnh của mỗi quái vật là một số nguyên từ \(0\) đến \(N-1\), kể cả hai đầu mút.
• Hai quái vật khác nhau không có cùng sức mạnh.

Bạn có thể chọn hai quái vật khác nhau và cho chúng giao đấu. Nếu quái vật \(a\) và quái vật \(b\) (\(0 \le a,b \le N-1\), \(a \ne b\)) giao đấu, kết quả được xác định như sau:

• Nếu \(|S_a-S_b|=1\), quái vật có sức mạnh nhỏ hơn thắng.
• Nếu \(|S_a-S_b|>1\), quái vật có sức mạnh lớn hơn thắng.

Bất kể thắng hay thua, cùng một quái vật có thể được cho giao đấu bao nhiêu lần tùy ý.

Ban đầu, bạn không biết sức mạnh của các quái vật. Bạn muốn xác định sức mạnh của từng quái vật bằng cách tổ chức không quá \(25\,000\) trận đấu và quan sát kết quả. Hơn nữa, bạn muốn sử dụng số trận đấu ít nhất có thể.

Cho số lượng quái vật, hãy viết chương trình xác định sức mạnh của từng quái vật thông qua các trận đấu.

Chi tiết cài đặt

Bạn cần nộp một tệp có tên monster.cpp. Tệp này phải dùng chỉ thị #include để nạp monster.h và cài đặt hàm sau:

std::vector<int> Solve(int N)

• Hàm được gọi đúng một lần trong mỗi bộ dữ liệu kiểm tra.
• Tham số N là số lượng quái vật.
• Hàm trả về một mảng mô tả sức mạnh của từng quái vật. Gọi mảng trả về là T.
• Độ dài của T phải bằng \(N\). Nếu không, chương trình bị chấm Wrong Answer [1].
• Mỗi phần tử của T phải nằm trong đoạn từ \(0\) đến \(N-1\). Nếu không, chương trình bị chấm Wrong Answer [2].
• Với mọi \(i\) (\(0 \le i \le N-1\)), phải có T[i] \(=S_i\). Nếu không, chương trình bị chấm Wrong Answer [3].

Chương trình của bạn có thể gọi hàm sau để cho hai quái vật giao đấu:

bool Query(int a, int b)

• Các tham số a, b là chỉ số của hai quái vật giao đấu.
• Hàm trả về true nếu quái vật \(a\) thắng, và false nếu quái vật \(b\) thắng.
• Phải có \(0 \le a,b \le N-1\). Nếu không, chương trình bị chấm Wrong Answer [4].
• Phải có \(a \ne b\). Nếu không, chương trình bị chấm Wrong Answer [5].
• Không được gọi Query quá \(25\,000\) lần. Nếu vượt quá giới hạn này, chương trình bị chấm Wrong Answer [6].

Lưu ý quan trọng

• Bạn được phép cài đặt các hàm khác để sử dụng nội bộ hoặc khai báo biến toàn cục.
• Chương trình của bạn không được sử 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. Tuy nhiên, bạn đượ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ử

Đề chính thức cho biết trang thi cung cấp một tệp nén chứa trình chấm mẫu và tệp mã nguồn mẫu dành cho chương trình của bạn.

Trình chấm mẫu là tệp grader.cpp. Để thử chương trình, đặt grader.cpp, monster.cpp, monster.h trong cùng một thư mục và dùng lệnh sau:

g++ -std=gnu++17 -O2 -o grader grader.cpp monster.cpp

Sau khi biên dịch thành công, tệp thực thi grader được tạo ra. Lưu ý rằng trình chấm thực tế khác với trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng:

N
S_0 ... S_{N-1}

Dữ liệu ra

Khi chương trình kết thúc bình thường, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn, không kèm dấu ngoặc kép:

• Nếu câu trả lời đúng, trình chấm ghi số lần gọi Query, chẳng hạn Accepted: 100.
• Nếu câu trả lời sai, trình chấm ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình vi phạm nhiều điều kiện, trình chấm mẫu chỉ báo một trong các loại lỗi đó.

Lưu ý về trình chấm

Trong một số bộ dữ liệu kiểm tra, trình chấm thực tế là thích nghi (adaptive). Điều này có nghĩa là trình chấm không cố định đáp án ngay từ đầu mà trả lời dựa trên các lần gọi Query trước đó. Tuy nhiên, luôn bảo đảm tồn tại ít nhất một đáp án phù hợp với tất cả các câu trả lời đã đưa ra.

Ràng buộc

• \(4 \le N \le 1\,000\).
• \(0 \le S_i \le N-1\) (\(0 \le i \le N-1\)).
• \(S_i \ne S_j\) (\(0 \le i<j \le N-1\)).

Phân nhóm

1. (10 điểm) \(N \le 200\).
2. (15 điểm) Trình chấm thực tế không thích nghi.

3. (75 điểm) Không có giới hạn bổ sung. Nếu chương trình trả lời đúng tất cả các bộ dữ liệu kiểm tra trong phân nhóm này, điểm được tính như sau. Gọi \(X\) là số lần gọi Query lớn nhất trên tất cả các bộ dữ liệu kiểm tra của phân nhóm:

4. Nếu \(10\,000<X\le25\,000\), điểm là \(\left\lfloor75\times\dfrac{25\,000-X}{15\,000}\right\rfloor\).

5. Nếu \(X\le10\,000\), điểm là \(75\).

Ví dụ giao tiếp

Sau đây là một đầu vào cho trình chấm mẫu và các lời gọi hàm tương ứng. Giá trị trả về của Solve không phải dữ liệu mà chương trình của bạn được phép ghi ra đầu ra chuẩn.

Ví dụ 1

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

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

5
3 1 4 2 0

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

Mảng trả về của Solve, không phải đầu ra chuẩn.

3 1 4 2 0

Các lời gọi hàm

Nguồn

JOI Open Contest 2021, JCIOI. Bản dịch tiếng Việt từ đề chính thức; phát hành theo giấy phép CC BY-SA 4.0.