CEOI 2023 - Ngày 1

Đề 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.

Đề bài

Sau lễ khai mạc thành công, Ủy ban Khoa học đang mong chờ ngày thi đầu tiên. Tuy nhiên, chủ tịch Ủy ban Kỹ thuật phát hiện hoạt động mạng đáng ngờ: dường như có người đang định tấn công máy chủ chấm bài.

Máy chủ chấm bài có năng lực tính toán \(c_G\). Kẻ tấn công muốn làm năng lực này giảm xuống không quá \(0\). Máy chủ còn được bảo vệ bởi \(f_G\) tường lửa; mỗi tường lửa làm giảm tác động của một đợt tấn công đi một lượng cố định \(S\).

Ở mỗi lượt của mình, kẻ tấn công chọn đúng một trong hai hành động:

• Hạ một tường lửa của máy chủ, làm \(f_G\) giảm vĩnh viễn đi \(1\) nhưng không thấp hơn \(0\).
• Dùng toàn bộ năng lực tính toán \(c_H\) của mình để tấn công máy chủ, làm \(c_G\) giảm vĩnh viễn đi

Chủ tịch có thể phản công bằng cách hạ một trong \(f_H\) tường lửa của kẻ tấn công, hoặc dùng năng lực tính toán của máy chủ để tấn công, làm \(c_H\) giảm đi

Hai bên luân phiên hành động và kẻ tấn công đi trước.

Ủy ban chưa biết năng lực tính toán và số tường lửa của kẻ tấn công. Đồng thời, do máy chủ vẫn có thể được nâng cấp, các thông số tương ứng của máy chủ cũng chưa xác định. Với mỗi trong \(Q\) kịch bản \((c_H,f_H,c_G,f_G)\), hãy cho biết liệu kẻ tấn công có thể hạ máy chủ hay không, ngay cả khi chủ tịch hành động tối ưu.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(S\) và \(Q\).

Mỗi trong \(Q\) dòng tiếp theo chứa bốn số nguyên \(c_H\), \(f_H\), \(c_G\), \(f_G\), lần lượt là năng lực tính toán và số tường lửa của kẻ tấn công, rồi của máy chủ chấm bài.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) chứa YES nếu trong kịch bản tương ứng, kẻ tấn công có thể làm năng lực tính toán của máy chủ giảm xuống không quá \(0\) bất kể chủ tịch hành động thế nào; ngược lại, in NO.

Ràng buộc

• \(1\le S\le 30\,000\).
• \(1\le c_H,c_G\le 10^{12}\).
• \(0\le f_H,f_G\le 10^{12}\).
• \(1\le Q\le 250\,000\).

Phân nhóm

• Subtask 1 (5 điểm): \(S,c_H,f_H,c_G,f_G\le 75\).
• Subtask 2 (5 điểm): \(S,c_H,f_H,c_G,f_G\le 300\).
• Subtask 3 (10 điểm): \(S=1\).
• Subtask 4 (25 điểm): \(S,c_H,f_H,c_G,f_G\le 2\,000\).
• Subtask 5 (20 điểm): \(S\le 400\).
• Subtask 6 (20 điểm): \(f_G,f_H\le 125\).
• Subtask 7 (15 điểm): Không có ràng buộc bổ sung.

Ví dụ

17 2
42 1 33 1
42 1 33 7

YES
NO

1 1
999999999999 999999999999 999999999999 999999999999

YES

2 1
1000000000000 0 1 1000000000000

NO

Đề bài

Ngày thi đầu tiên đầy hỗn loạn đã kết thúc. Dù Ủy ban Khoa học vừa kịp ngăn cuộc tấn công vào máy chủ chấm bài, họ lo rằng việc chấm các bài nộp đã bị ảnh hưởng. Chỉ còn một cách: chấm lại tất cả bài nộp.

Máy chủ có \(N\) lõi xử lý. Ủy ban đã gán cho mỗi lõi một danh sách gồm \(S\) bài nộp; mỗi bài thuộc một trong \(T\) bài toán, được đánh số từ \(1\) đến \(T\). Giá trị \(S\) là một lũy thừa dương của \(2\). Trong \(S\) phút tiếp theo, mỗi lõi sẽ chấm đúng một bài trong danh sách của nó ở mỗi phút.

Cơ sở dữ liệu chứa dữ liệu đề khá mong manh và có thể sập nếu số yêu cầu đồng thời cho dữ liệu của cùng một bài biến động quá nhiều. Vì vậy, Ủy ban muốn sắp thứ tự các bài nộp trên từng lõi sao cho trong suốt quá trình chấm lại, đối với mỗi bài toán, chênh lệch giữa số bài nộp được chấm đồng thời lớn nhất và nhỏ nhất không quá \(1\).

Hãy tính một cách sắp thứ tự thỏa mãn yêu cầu.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N\), \(S\) và \(T\).

Mỗi trong \(N\) dòng tiếp theo mô tả danh sách bài nộp đã gán cho một lõi. Dòng thứ \(i\) chứa \(S\) số nguyên \(t_1,t_2,\ldots,t_S\) (\(1\le t_j\le T\)), cho biết lõi thứ \(i\) được gán các bài nộp thuộc những bài toán đó.

Dữ liệu ra

In \(N\) dòng mô tả một cách sắp thứ tự hợp lệ. Dòng thứ \(i\) chứa \(S\) số nguyên \(r_1,r_2,\ldots,r_S\); lõi thứ \(i\) sẽ chấm một bài thuộc bài toán \(r_j\) trong phút thứ \(j\).

Với mỗi lõi, dãy được in phải là một hoán vị của danh sách bài toán trên dòng tương ứng của dữ liệu vào. Đối với mỗi bài toán, chênh lệch giữa số bài nộp thuộc bài đó được chấm đồng thời lớn nhất và nhỏ nhất qua \(S\) phút phải không quá \(1\).

Dữ liệu bảo đảm luôn tồn tại ít nhất một cách sắp hợp lệ.

Ràng buộc

• \(S=2^k\) với một số nguyên dương \(k\).
• \(1\le N,S,T\le 100\,000\).
• \(N\cdot S\le 500\,000\).

Phân nhóm

• Subtask 1 (10 điểm): \(S=2\) và \(N,T\le20\).
• Subtask 2 (25 điểm): \(S=2\). Subtask gồm ba nhóm lần lượt trị giá \(15\), \(5\) và \(5\) điểm.
• Subtask 3 (25 điểm): \(N\cdot S\le10\,000\). Subtask gồm ba nhóm lần lượt trị giá \(15\), \(5\) và \(5\) điểm.
• Subtask 4 (40 điểm): Không có ràng buộc bổ sung. Subtask gồm ba nhóm lần lượt trị giá \(20\), \(10\) và \(10\) điểm.

Trong các Subtask 2, 3 và 4:

• Nhóm 1: \(T\le N\) và tổng số bài nộp của mỗi bài toán chia hết cho \(S\).
• Nhóm 2: \(T\le N\), không còn yêu cầu chia hết. Điểm nhóm này được cộng thêm vào Nhóm 1.
• Nhóm 3: Không có ràng buộc bổ sung. Điểm nhóm này được cộng thêm vào hai nhóm trước.

Ví dụ

3 2 3
1 2
2 3
2 3

2 1
3 2
2 3

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

2 2 2 3
3 2 3 2
2 3 2 2