Mofk Cup Round 1 - ARTS
Xem dạng PDF
Ban tổ chức Mofk Cup quyết định tổ chức ~1~ buổi văn nghệ. Ở một tiết mục, họ cử ra ~n~ cặp bạn, cặp bạn đồng hành thứ ~i~ có chiều cao ~i~. Tiết mục này ~2n~ người trên sẽ xếp thành ~1~ hàng ngang. Sẽ có một số vị trí quan trọng, được gọi là "spotlight", được đánh số ~1~, và các vị trí còn lại được đánh số ~0~.
Hàng ~2n~ người trên sẽ được gọi là đẹp nếu ở mỗi vị trí spotlight, người đứng ở đó có thể nhìn thấy bạn đồng hành cùng cặp của mình, và những vị trí không phải spotlight thì không thể nhìn thấy bạn đồng hành cùng cặp của mình. ~2~ người trong cùng ~1~ cặp đôi được gọi là nhìn thấy nhau nếu tất cả mọi người ở các vị trí giữa họ đều có chiều cao thấp hơn họ. Nói cách khác, nếu ~2~ người trong cùng ~1~ cặp đôi đứng ở vị trí ~L~ và ~R~, thì: ~h_L= h_R > max(h_{L+1},h_{L+2},...,h_{R-1})~.
Hãy giúp ban tổ chức xem có cách để xếp ~2n~ người trên vào hàng sao cho hàng đó được coi là đẹp hay không. Nếu có, hãy in ra ~1~ cách bất kì.
Input
Dòng đầu tiên gồm một số nguyên dương ~n~ là số lượng cặp đôi ~(1 \leq n \leq 5\times10^5)~.
Dòng thứ hai là một chuỗi ký tự độ dài ~2n~ chỉ bao gồm 2 loại ký tự '0' và '1'. Người ở vị trí ~i~ sẽ nhìn thấy bạn đồng hành của mình khi ký tự thứ ~i~ là '1'.
Output
Ở dòng đầu tiên, nếu có tồn tại kết quả thì in ra "YES", không thì "NO" (in ra không có dấu nháy đôi và không quan trọng in hoa).
Nếu có tồn tại kết quả thì in ra dòng thứ 2 bao gồm ~2n~ số nguyên dương. Số thứ ~i~ là chiều cao của người thứ ~i~ và thỏa mãn yêu cầu đề bài.
Scoring
~20\%~ số test có: ~0 < n \le 20~.
~30\%~ số test khác có ~0 < n \le 3000~.
~50\%~ số test còn lại không có ràng buộc gì thêm.
Sample Input 1
5
1000100000
Sample Output 1
YES
5 4 3 2 5 1 4 3 2 1
Bình luận
Mình xin trình bày cách chọn dãy đơn giản hơn so với cách trong editorial Đầu tiên với các vị trí 1 thì ta điền các số lớn nhất từ ngoài vào trong. vd có 4 vị trí 1 thì ta sẽ điền 5 4 4 5 lần lượt vào các vị trí đó. Sau đó gọi q là số lớn nhất còn lại. ta sẽ tạo 1 dãy số gồm các số tăng dần từ 1 đến q sau đó giảm dần từ q-1 về 1. còn 1 số q nữa thì nếu dãy con cuối cùng chỉ toàn số 0 có độ dài lớn hơn q thì ta sẽ cho số q còn lại vào đầu dãy vừa tạo. còn lại thì ta cho vào cuối. sau đó dùng 2 con trỏ ta có thể dễ dàng điền dãy số vừa tạo vào dãy cần tìm. trong test mẫu thì dãy con liên tiếp toàn 0 ở cuối có độ dài là 5, lớn hơn số còn lại là 4, suy ra ta sẽ chuyển số 4 ra đầu, thu được dãy 4 1 2 3 4 3 2 1. kết hợp với các vị trí spotlight ta đc dãy 5 4 1 2 5 3 4 3 2 1 (lưu ý là nếu cả 2 dãy đầu tiên và cuối cùng đều <=q thì ta vẫn phải thực hiện việc dịch số) Chứng minh: dãy đã chọn có tính đối xứng tức sẽ luôn luôn có ít nhất 1 số lớn hơn x ở giữa x và số x còn lại. và 2 số lớn nhất không ở vị trí 1 sẽ không bao giờ ở chung trong cùng 1 dãy vì ta đã chuyển số còn lại ra khỏi vùng ảnh hưởng của số ở chính giữa, trường hợp 2 số lớn nhất chung dãy bây giờ chỉ có thể xảy ra khi mà tất cả các số 0 đứng liền nhau, mà trường hợp đó ta đã loại từ đầu rồi nên chắc chắn dãy đã chọn thỏa mãn Note: mình không hiểu cách làm trong editorial nên không chắc cách này có khác cách trong editorial không. nhưng mình nghĩ cách này dễ hiểu hơn