trang chủ / đề bài / icpc25_mb_k

Du lịch

Đề bài

Mô tả

Ở một đất nước xa xôi có một du khách tên Thanh, người mong muốn đạp xe du lịch khắp đất nước. Đất nước có n thành phố, đánh số từ 1 đến n. Mỗi thành phố hoặc không có điểm tham quan nào mà Thanh muốn ghé, hoặc có đúng 1 điểm tham quan mà Thanh muốn ghé.

Thanh đã sắp xếp một lộ trình đi qua tất cả các thành phố: thành phố thứ 1 trên lộ trình là A1, thành phố thứ i là Ai, và chuyến đi kết thúc khi đến thành phố An. Thanh muốn hoàn thành chuyến đi trong đúng m tháng (m<n), nên cần lên kế hoạch hợp lý.

Khi Thanh đến một thành phố, nếu thành phố đó có điểm tham quan mà anh muốn ghé, anh nhận được 1 điểm vui; ngược lại anh nhận 1 điểm buồn. Một tháng đủ để anh đi qua bao nhiêu thành phố tùy ý, nhưng anh cũng muốn nghỉ ngơi một chút. Thanh luôn nghỉ tại thành phố cuối cùng anh đến trong tháng đó (nếu thành phố này có điểm tham quan, anh luôn tham quan trước khi nghỉ). Thanh muốn mỗi tháng đều có kế hoạch đi, tức là mỗi tháng anh đến ít nhất một thành phố mới.

Thanh cần lập một lịch trình đi và nghỉ, tức là một dãy x1,x2,…,xm, trong đó xi là số hiệu thành phố nơi Thanh nghỉ trong tháng thứ i. Vì chuyến đi kết thúc sau tháng cuối cùng nên xm=An. Ví dụ: n=5, m=3, (A1,…,A5)=(3,2,4,1,5), (x1,x2,x3)=(2,1,5) nghĩa là: tháng 1 anh đến thành phố 3 và 2, nghỉ ở thành phố 2; tháng 2 anh đến thành phố 4 và 1, nghỉ ở thành phố 1; tháng 3 anh đến thành phố 5 và nghỉ ở đó. Có nhiều lịch trình như vậy.

Với một lịch trình K, gọi di là giá trị tuyệt đối của hiệu giữa số điểm vui và số điểm buồn nhận được trong tháng thứ i. Giá trị lớn nhất trong dãy d1,d2,…,dm được gọi là CK.

Thanh muốn chọn lịch trình có CK nhỏ nhất. Có thể có nhiều lịch trình cùng đạt CK nhỏ nhất; khi đó anh muốn chọn lịch trình có thứ tự từ điển nhỏ nhất. So sánh thứ tự từ điển của hai dãy là so sánh tại vị trí khác nhau đầu tiên, chẳng hạn (1,2,3,4)<(1,2,4,3).

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên dương n và m: số thành phố và số tháng du lịch.
  • n dòng tiếp theo, dòng thứ i gồm hai số nguyên Ai và Bi: Ai là số hiệu thành phố thứ i trên lộ trình; Bi=1 nếu thành phố Ai có điểm tham quan Thanh thích, Bi=0 nếu không. Các giá trị Ai đôi một khác nhau, tức là A1,…,An là một hoán vị của 1,…,n.

Dữ liệu ra

In ra trên một dòng m số nguyên dương x1,x2,…,xm: lịch trình tìm được.

Ràng buộc

  • 1≤m<n≤5·105, m≤2·105
  • A1,…,An là một hoán vị của 1,…,n; Bi∈{0,1}

Ví dụ

Input Output Giải thích
8 3
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0
1 6 8 Tháng 1 có 2 điểm vui và 2 điểm buồn, tháng 2 có 1 điểm vui và 1 điểm buồn, tháng 3 có 1 điểm vui và 1 điểm buồn, nên CK=0, nhỏ nhất có thể. Các lịch trình đạt được là 1 6 8, 3 6 8, 3 1 8; nhỏ nhất theo thứ tự từ điển là 1 6 8.
5 3
3 1
2 1
4 0
1 1
5 1
3 1 5 Ví dụ bổ sung. Tổng điểm vui trừ điểm buồn là 3 nên CK≥1; lịch trình 3 1 5 chia thành các tháng (3), (2,4,1), (5) với d=1,1,1.

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