Những lớp bị mất
Đề bài
Mô tả
Linh đang khôi phục một dự án video có tệp bị hỏng. Dự án có đoạn phim (clip), đánh số từ đến . Mỗi clip nằm trên một lớp (layer) riêng, và các lớp được xếp chồng lên nhau: khi nhiều clip cùng xuất hiện trên màn hình ở cùng một khung hình, clip ở lớp cao hơn sẽ che các clip ở bên dưới. Clip xuất hiện trên màn hình ở các khung hình , tính cả và .
Khoảng khung hình của các clip vẫn còn nguyên, nhưng thứ tự của các lớp đã bị mất. Linh vẫn còn nhật ký của trình kết xuất xem trước (preview renderer). Mỗi dòng của nhật ký là một ảnh chụp (snapshot) được lấy tại một khung hình nào đó. Nó liệt kê các clip đang xuất hiện trên màn hình ở khung hình , bắt đầu từ lớp trên cùng đi xuống, nhưng dừng lại sau clip đầu tiên. Giá trị có thể khác nhau giữa các ảnh chụp. Nó có thể bằng , và có thể bằng số clip đang có trên màn hình, khi đó tất cả các clip đều được liệt kê.
Hãy giúp Linh tìm một thứ tự của cả lớp, từ trên xuống dưới, phù hợp với mọi ảnh chụp. Một thứ tự phù hợp với ảnh chụp nếu điều sau đúng: lấy các clip có và sắp xếp chúng từ trên xuống dưới theo thứ tự đó; khi đó clip đầu tiên lần lượt là , đúng theo thứ tự này. Nói riêng, nếu thì mọi clip đang có trên màn hình ở khung hình mà không thuộc đều phải nằm dưới clip . Một ảnh chụp có không đặt ra ràng buộc nào lên thứ tự.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên (): số clip.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và (): khung hình đầu tiên và khung hình cuối cùng của clip .
- Dòng tiếp theo chứa một số nguyên (): số ảnh chụp.
- Mỗi dòng trong dòng tiếp theo mô tả một ảnh chụp. Dòng bắt đầu bằng hai số nguyên và (, ): khung hình của ảnh chụp và số clip được liệt kê. Tiếp theo là số nguyên (): các clip được liệt kê từ trên xuống dưới. Các clip đôi một phân biệt, và mỗi clip trong số đó đều đang xuất hiện trên màn hình ở khung hình . Nếu , dòng chỉ chứa và .
Các ảnh chụp được cho theo thứ tự không giảm; có thể có nhiều ảnh chụp ở cùng một khung hình. Tổng các giá trị trên mọi ảnh chụp không vượt quá .
Dữ liệu đảm bảo có ít nhất một thứ tự phù hợp với mọi ảnh chụp.
Dữ liệu ra
In ra số nguyên phân biệt : số hiệu các clip từ lớp trên cùng đến lớp dưới cùng. Nếu có nhiều thứ tự phù hợp với mọi ảnh chụp, in ra thứ tự bất kỳ.
Ràng buộc
- , .
- .
- , , các ảnh chụp có không giảm.
- Tổng các giá trị không vượt quá .
- Các clip được liệt kê trong một ảnh chụp đôi một phân biệt và đều xuất hiện trên màn hình ở khung hình của ảnh chụp đó.
- Luôn tồn tại ít nhất một thứ tự phù hợp.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 6 0 4 4 9 6 8 1 10 4 1 1 2 4 1 3 6 1 4 9 2 3 5 |
4 3 2 5 1 | Ở khung hình , clip và xuất hiện, nên clip ở trên clip . Ở khung hình , các clip xuất hiện (clip kết thúc và clip bắt đầu ở khung hình này), và clip ở trên cùng. Ở khung hình , các clip xuất hiện (clip kết thúc và clip bắt đầu ở khung hình này), và clip ở trên cùng. Ở khung hình , chỉ có clip và xuất hiện, và ảnh chụp liệt kê cả hai. Ngoài thứ tự trong ví dụ, các thứ tự 4 3 1 2 5 và 4 3 2 1 5 cũng được chấp nhận. |
| 4 0 5 5 10 3 7 20 30 4 0 0 5 1 3 5 2 3 2 12 0 |
3 2 4 1 | Các ảnh chụp ở khung hình và không liệt kê clip nào, còn hai ảnh chụp ở khung hình thấy các clip . Gộp lại, chúng cho biết clip ở trên clip , và clip ở trên clip . Không ảnh chụp nào thấy clip , nên clip có thể nằm ở vị trí bất kỳ trong thứ tự. |
Bình luận