Boris và Ihor nhận một dãy \(a_0,a_1,\ldots,a_{N-1}\) gồm các số nguyên dương. Bạn biết toàn bộ dãy, sau đó xét các phần tử từ trái sang phải và phải giao mỗi phần tử cho đúng một trong hai người.

Theo thứ tự nhận, dãy của mỗi người phải tăng nghiêm ngặt. Phần tử đầu tiên của một người có thể có giá trị bất kỳ và một người có thể không nhận phần tử nào.

Với mỗi \(K\) từ \(0\) đến \(N\), hãy xác định độc lập xem có thể chia dãy sao cho Boris nhận đúng \(K\) phần tử hay không.

Giao diện thư viện

Submission C++ phải include increasing.h và cài đặt:

std::vector<bool> increasing_split(std::vector<int> a);

Hàm được gọi đúng một lần. Nó phải trả về vector có đúng \(N+1\) phần tử; phần tử thứ \(K\) là true khi cách chia tương ứng tồn tại.

Dữ liệu vào

Submission không đọc standard input. Sample grader đọc \(N\) rồi dãy \(a\).

Dữ liệu ra

Submission không ghi standard output. Kết quả được trả qua increasing_split.

Ràng buộc

• \(2\le N\le4\cdot10^5\).
• \(1\le a_i\le10^9\).

Phân nhóm

1. \(10\) điểm: \(N\le18\).
2. \(5\) điểm: \(a_i\le a_{i+1}\) với mọi \(0\le i<N-1\).
3. \(5\) điểm: \(a_0\ge\max(a_1,\ldots,a_{N-1})\).
4. \(16\) điểm: \(a\) là hoán vị của \(1,\ldots,N\); với mọi \(i\) thỏa \(a_i<a_{i+1}\), tiền tố \(a_0,\ldots,a_i\) là hoán vị của \(1,\ldots,i+1\).
5. \(21\) điểm: \(N\le5000\); \(a\) là hoán vị của \(1,\ldots,N\); với mọi \(i\) thỏa \(\max(a_0,\ldots,a_i)<a_{i+1}\), tiền tố \(a_0,\ldots,a_i\) là hoán vị của \(1,\ldots,i+1\).
6. \(17\) điểm: \(N\le4\cdot10^5\); \(a\) là hoán vị của \(1,\ldots,N\); với mọi \(i\) thỏa \(\max(a_0,\ldots,a_i)<a_{i+1}\), tiền tố \(a_0,\ldots,a_i\) là hoán vị của \(1,\ldots,i+1\).
7. \(16\) điểm: \(N\le5000\).
8. \(10\) điểm: không có ràng buộc thêm.

Ví dụ

5
3 1 4 5 5

001100

4
1 2 3 4

11111

Nguồn

EJOI 2026 - Ngày 1, Increasing Split.

Đề bài EJOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).