Có \(N\) ô liên tiếp, đánh số \(0,\ldots,N-1\), với độ cao \(p_i\) tạo thành một hoán vị của \(0,\ldots,N-1\). Hai ô là gần nhau khi khoảng cách chỉ số không quá \(1\).

Robot nhận hai loại lệnh. MAX chuyển robot đến ô cao nhất trong các ô gần vị trí hiện tại; MIN chuyển đến ô thấp nhất. Ô hiện tại cũng được xét nên robot có thể đứng yên.

Mỗi truy vấn cho một tập vị trí bắt đầu. Hãy xác định có tồn tại một chuỗi hữu hạn các lệnh MIN/MAX đưa robot đến cùng một ô cuối, bất kể vị trí bắt đầu được chọn trong tập hay không. Không cần dựng chuỗi lệnh.

Giao diện thư viện

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

void initialize(std::vector<int> p);
bool exists_program(std::vector<int> x);

initialize được gọi đúng một lần. Sau đó exists_program được gọi \(Q\) lần; x chứa các chỉ số theo thứ tự tăng nghiêm ngặt.

Dữ liệu vào

Submission không đọc standard input. Sample grader đọc \(N,Q\), hoán vị \(p\), rồi từng truy vấn.

Dữ liệu ra

Submission không ghi standard output. Mỗi đáp án được trả từ exists_program.

Ràng buộc

• \(3\le N\le2\cdot10^5\).
• \(1\le Q\le5\cdot10^5\).
• \(p\) là hoán vị của \(0,\ldots,N-1\).
• \(2\le K_i\le N\) và \(0\le x_0<\cdots<x_{K_i-1}<N\).
• Tổng \(K_i\) trên mọi truy vấn không quá \(10^6\).

Phân nhóm

1. \(3\) điểm: \(K_i=2\); nếu đáp án dương thì tồn tại chương trình đúng một lệnh.
2. \(7\) điểm: \(K_i=2\); nếu đáp án dương thì tồn tại chương trình không quá năm lệnh.
3. \(9\) điểm: \(N\le100\), \(Q\le500\), \(K_i=2\).
4. \(17\) điểm: \(N\le5000\), \(K_i=2\).
5. \(7\) điểm: \(K_i=2\) và \(x_1=x_0+1\).
6. \(8\) điểm: \(N\le5000\).
7. \(13\) điểm: tồn tại \(0<a<b<N-1\) sao cho \(p_0<\cdots<p_a>p_{a+1}>\cdots>p_b<p_{b+1}<\cdots<p_{N-1}\).
8. \(13\) điểm: độ cao xen kẽ \(p_0<p_1>p_2<\cdots\); dấu cuối là < nếu \(N\) chẵn và > nếu \(N\) lẻ.
9. \(23\) điểm: không có ràng buộc thêm.

Ví dụ

3 3
0 2 1
2 0 2
3 0 1 2
2 1 2

111

7 3
0 4 2 1 3 5 6
3 0 1 3
3 1 3 4
2 3 6

001

Nguồn

EJOI 2026 - Ngày 2, Automata.

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