trang chủ / đề bài / icpc24_mb_d

Hoàn thành công việc

Đề bài

Mô tả

Tuệ được giao n công việc, đánh số từ 1 đến n. Mỗi ngày, Tuệ làm các công việc còn dang dở từ những ngày trước theo quy tắc sau:

  • Công việc đầu tiên trong ngày: Tuệ được chọn một công việc bất kỳ chưa hoàn thành và bắt đầu làm.
  • Nếu đã chọn công việc i, sau khi hoàn thành công việc i, công việc j tiếp theo được chọn phải thỏa mãn j>ai (và chưa hoàn thành).
  • Nếu sau công việc i không còn công việc nào hợp lệ để chọn, Tuệ phải đợi đến ngày hôm sau mới làm tiếp.

Để nhận được lương, Tuệ phải hoàn thành cả n công việc, vì vậy Tuệ muốn làm xong tất cả trong ít ngày nhất có thể. Hãy viết chương trình xác định số ngày ít nhất cần thiết để Tuệ hoàn thành mọi công việc, và với mỗi ngày, đưa ra thứ tự các công việc được làm trong ngày đó.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n (1≤n≤3·105).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (0≤ai≤n).

Dữ liệu ra

  • Dòng đầu tiên in số nguyên d: số ngày ít nhất cần thiết để hoàn thành cả n công việc.
  • d dòng tiếp theo: dòng thứ t bắt đầu bằng số kt, tiếp theo là kt số là các công việc được hoàn thành trong ngày thứ t, theo đúng thứ tự làm. Nếu có nhiều cách hoàn thành trong số ngày ít nhất, in ra cách bất kỳ.

Ràng buộc

  • 1≤n≤3·105
  • 0≤ai≤n

Ví dụ

Input Output Giải thích
4
2 2 4 4
2
2 2 4
2 1 3
Ngày thứ nhất làm công việc 2 rồi 4 (vì 4>a2=2). Ngày thứ hai làm công việc 1 rồi 3 (vì 3>a1=2).
5
5 0 1 2 3
1
5 5 4 3 2 1
Làm tất cả trong một ngày: 4>a5=3, 3>a4=2, 2>a3=1, 1>a2=0.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0