trang chủ / đề bài / icpc23_nat_l

Thứ hạng thấp nhất

Đề bài

Mô tả

Năm 2050. Sau nhiều lần trì hoãn vì những hoàn cảnh bất thường, Cuộc thi Sửa ống nước Hợp tác Liên lục địa (Intercontinental Cooperative Plumbing Competition, ICPC) cuối cùng cũng được tổ chức! Tham gia cuộc thi có n đội thợ sửa ống nước, đã vượt qua các vòng thi khu vực từ năm 2021 cho đến tận năm 2049. Theo truyền thống, ICPC gồm m bài toán sửa ống nước, các đội thi đấu để giải được càng nhiều bài càng tốt. Tuy nhiên, khác với những cuộc thi khác có cùng tên viết tắt, chỉ đội đầu tiên giải được một bài mới nhận được một điểm cho bài đó. Sau khi mọi bài đã được giải, các đội được xếp hạng từ 1 đến n theo số điểm, các đội có cùng số điểm nhận cùng thứ hạng. Cụ thể, với mỗi đội i, thứ hạng ri của đội bằng số đội j có số điểm lớn hơn hẳn số điểm của đội i, cộng thêm 1. Ví dụ, nếu có 5 đội thi 6 bài và các đội giải được đầu tiên lần lượt là 1,2,1,4,5 và 1, thì bảng xếp hạng như sau:

  • Hạng 1: đội 1 (3 điểm).
  • Hạng 2: các đội 2, 4 và 5 (1 điểm).
  • Hạng 5: đội 3 (0 điểm).

Ban tổ chức đã chuẩn bị m bài toán. Vì mỗi đội có những điểm mạnh và điểm yếu rất riêng, ban tổ chức biết chắc chắn rằng đội ai sẽ là đội đầu tiên giải được bài i. Không may là, do hoàn cảnh bất thường (lại nữa!), cuộc thi phải rút ngắn. Ban tổ chức quyết định chọn không quá k bài liên tiếp cho cuộc thi. Nói cách khác, họ chọn hai chỉ số f, l sao cho 1≤f≤l≤m và 1≤l−f+1≤k, rồi chọn các bài f,f+1,…,l cho cuộc thi.

Là một thành viên ban tổ chức và từng là thợ sửa ống nước, MofK rất háo hức muốn biết mỗi đội có thể nhận được những thứ hạng nào. Đội nào cũng có thể vô địch, nhưng tìm thứ hạng thấp nhất (bi quan nhất) có thể của mỗi đội lại không hề đơn giản. Hãy giúp anh ấy trả lời câu hỏi đầy thử thách này!

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, m và k (1≤n≤10000, 1≤k≤m≤10000): số đội thi, số bài đã chuẩn bị và giới hạn số bài của cuộc thi.
  • Dòng thứ hai chứa m số nguyên a1,a2,…,am (1≤ai≤n): đội đầu tiên giải được mỗi bài.

Dữ liệu ra

In ra n số nguyên r1,r2,…,rn trên một dòng, cách nhau bởi dấu cách, trong đó ri là thứ hạng thấp nhất có thể của đội i trong mọi cách chọn bài.

Ràng buộc

  • 1≤n≤10000
  • 1≤k≤m≤10000
  • 1≤ai≤n

Ví dụ

Input Output Giải thích
4 5 5
1 1 2 3 4
4 3 3 4 Vì k=m=5, có thể chọn mọi đoạn bài liên tiếp. Đội 1 đứng cuối nếu chọn các bài [3,4,5]. Đội 2 đứng thứ ba nếu chọn các bài [4,5], và không có cách nào để đội 2 đứng cuối. Đội 3 đứng thứ ba nếu chọn các bài [2,3], và không có cách nào để đội 3 đứng cuối. Đội 4 đứng cuối nếu chọn các bài [2,3,4].
5 5 5
1 1 3 2 2
3 3 3 4 4 Đội 3 đứng thứ ba nếu chọn cả 5 bài (các đội 1 và 2 được 2 điểm, đội 3 được 1 điểm); mọi đoạn không chứa bài 3 chỉ có một đội ghi điểm. Các đội 4 và 5 không giải được bài nào; nếu chọn cả 5 bài thì có 3 đội xếp trên họ.

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