Đề bài

Ủy ban Khoa học đang thư giãn tại lễ khai mạc CEOI. Các bài thi đã sẵn sàng, \(10^{12}\) tường lửa của máy chủ chấm bài cuối cùng cũng hoạt động, và Ủy ban mong chờ một màn biểu diễn với những ngọn đuốc rực lửa. Nhưng không ai mua đủ dầu cho các ngọn đuốc, nên Ủy ban cần bạn giúp điều hành buổi diễn mà không dùng cạn dầu.

Trong buổi diễn, các nghệ sĩ đứng thành một hàng và được đánh số từ trái sang phải, bắt đầu từ \(1\). Số nghệ sĩ thay đổi theo thời gian. Mỗi người cầm một ngọn đuốc, có thể đang cháy hoặc đã tắt. Ban đầu chỉ có một nghệ sĩ và đuốc của người đó đang cháy.

Buổi diễn gồm \(Q\) tiết mục. Đầu tiết mục \(a\), một trong hai sự kiện sau xảy ra ngoài tầm kiểm soát của Ủy ban:

• \(p_a>0\) nghệ sĩ mới vào cuối hàng bên phải; hoặc
• \(p_a>0\) nghệ sĩ ngoài cùng bên phải rời hàng.

Nghệ sĩ ngoài cùng bên trái luôn ở lại sân khấu. Đuốc của nghệ sĩ mới chưa cháy; nghệ sĩ rời sân khấu sẽ dập đuốc nếu đuốc đang cháy.

Khi hàng nghệ sĩ của tiết mục \(a\) đã sẵn sàng, Ủy ban công bố một số \(t_a\ge0\). Sau đó, mỗi nghệ sĩ có đuốc đang cháy truyền lửa cho \(t_a\) người ở bên phải mình. Nói cách khác, sau bước này, đuốc của nghệ sĩ \(i\) cháy khi và chỉ khi trước đó có ít nhất một đuốc đang cháy trong các vị trí

Để buổi diễn sinh động, phải có \(t_a\le5p_a\) và nên chọn \(t_a\) càng nhỏ càng tốt theo phần chấm điểm.

Cuối mỗi tiết mục, Ủy ban phải quyết định những đuốc đang cháy nào được giữ lại và những đuốc nào bị dập. Sau quyết định này:

• Đuốc của nghệ sĩ ngoài cùng bên phải phải luôn cháy.
• Không được còn quá \(150\) đuốc đang cháy.

Hãy viết chương trình chỉ dẫn Ủy ban điều hành buổi diễn theo các yêu cầu trên.

Giao tiếp

Đây là bài giao tiếp. Bạn phải nộp mã nguồn C++ cài đặt ba hàm sau và khai báo chúng bằng cách #include "light.h":

void prepare();
std::pair<long long, std::vector<long long>> join(long long p);
std::pair<long long, std::vector<long long>> leave(long long p);

Hàm prepare

void prepare();

Trình chấm gọi hàm này đúng một lần ở đầu mỗi bộ kiểm thử. Bạn có thể thực hiện khởi tạo trong hàm hoặc không làm gì.

Hàm join

std::pair<long long, std::vector<long long>> join(long long p);

Trình chấm gọi hàm này khi \(p=p_a>0\) nghệ sĩ mới vào cuối hàng bên phải.

Hàm phải trả về cặp \((t_a,L)\), trong đó:

• \(t_a\) là số được Ủy ban công bố;
• \(L\) là danh sách chỉ số của chính xác những nghệ sĩ có đuốc được giữ cháy ở cuối tiết mục.

Các phần tử của \(L\) phải tăng nghiêm ngặt.

Hàm leave

std::pair<long long, std::vector<long long>> leave(long long p);

Trình chấm gọi hàm này khi \(p=p_a>0\) nghệ sĩ ngoài cùng bên phải rời hàng. Giá trị trả về có cùng ý nghĩa và yêu cầu như đối với join.

Quy tắc hợp lệ

Trong mỗi lời gọi join hoặc leave:

• \(0\le t_a\le5p_a\).
• Danh sách trả về phải tăng nghiêm ngặt và chỉ chứa các chỉ số từ \(1\) đến số nghệ sĩ hiện có.
• Danh sách có nhiều nhất \(150\) phần tử.
• Nghệ sĩ ngoài cùng bên phải phải thuộc danh sách.
• Mỗi đuốc được liệt kê phải thực sự đã được thắp bởi quy tắc truyền lửa của tiết mục đó; bạn chỉ có thể dập bớt các đuốc đang cháy, không thể tự ý thắp thêm.

Nếu một giá trị trả về vi phạm bất kỳ yêu cầu nào, chương trình bị dừng ngay và bộ kiểm thử đó bị chấm sai.

Không được đọc từ đầu vào chuẩn hoặc ghi ra đầu ra chuẩn. Làm vậy có thể nhận kết quả Security violation!. Bạn được phép ghi ra luồng lỗi chuẩn (stderr).

Ràng buộc

Gọi \(N\) là số nghệ sĩ lớn nhất cùng đứng trong hàng tại bất kỳ thời điểm nào.

• \(N\le10^{17}\).
• \(1\le Q\le50\,000\).

Phân nhóm

• Subtask 1 (5 điểm): Chỉ có đúng một lời gọi leave trong mỗi bộ kiểm thử.
• Subtask 2 (5 điểm): \(N\le700\).
• Subtask 3 (10 điểm): \(N\le5\,000\).
• Subtask 4 (5 điểm): \(N\le25\,000\).
• Subtask 5 (10 điểm): \(N\le100\,000\).
• Subtask 6 (5 điểm): \(N\le500\,000\).
• Subtask 7 (60 điểm): Không có ràng buộc bổ sung.

Trong Subtask 7, điểm thực nhận phụ thuộc vào giá trị lớn nhất của \(t_a/p_a\) qua tất cả các tiết mục:

Đặc biệt, để nhận đủ điểm, mọi lời gọi join và leave phải thỏa mãn \(t_a\le p_a\).

Ví dụ giao tiếp

Xét một bộ kiểm thử có \(Q=4\). Một phiên giao tiếp có thể diễn ra như sau:

Chuỗi lời gọi trên là một bộ kiểm thử hợp lệ trong mọi subtask.

Trình chấm mẫu

Để thử chương trình cục bộ, liên kết lời giải với sample_grader.cpp và light.h.

Trình chấm mẫu đọc số nguyên \(Q\). Sau khi gọi prepare(), với mỗi tiết mục nó đọc một số nguyên khác \(0\):

• Số dương \(p_a\) khiến trình chấm gọi join(p_a).
• Số âm \(q_a\) biểu thị \(p_a=-q_a\) người rời hàng và khiến trình chấm gọi leave(p_a).

Trình chấm mẫu in biên bản các lời gọi và có thể kết thúc bằng một trong các thông báo sau:

• Invalid input: dữ liệu cho trình chấm không đúng định dạng.
• The stage is empty: sau một sự kiện, không còn nghệ sĩ nào.
• Invalid return value: \(t_a\) hoặc danh sách trả về không hợp lệ.
• Too many burning torches: còn quá \(150\) đuốc cháy.
• Rightmost torch not on fire: đuốc ngoài cùng bên phải không cháy hoặc đã bị dập.
• Not all announced torches have been lit: ít nhất một đuốc trong danh sách chưa được thắp theo quy tắc.
• Correct: ratio at most f, at most b burning torches: không có lỗi; mọi lời gọi thỏa \(t_a\le f\cdot p_a\) (sai số làm tròn được bỏ qua), và nhiều nhất \(b\) đuốc cùng cháy.

Trình chấm chính thức chỉ trả về Not correct, Security violation!, Partially correct hoặc Correct. Trình chấm chính thức có tính thích nghi: số nghệ sĩ vào hoặc rời trong một tiết mục có thể phụ thuộc vào hành vi của chương trình ở lần chạy hiện tại cũng như các lần chạy trước. Cả trình chấm mẫu lẫn trình chấm chính thức đều tự động dừng chương trình ngay khi phát hiện lỗi.