Masala G
Rost/Yolg'on o'yini
Sizda \(N\) ta karta mavjud. \(i-\) karta ustiga \(a_i\) soni yozilgan. Kartani joylashtirishga qarab, karta o'zida rost yoki yolg'on ma'lumot saqlashi mumkin. Har bir kartaning rost yoki yolg'on ma'lumot saqlashi quyidagiga ko'ra aniqlanadi:
- \(i-\) kartadan pastda kamida \(a_i\) ta yolg'on karta mavjud.
Sizga \(K\) butun soni beriladi. Kartalarni shunday joylashtiringki, tartiblashdan so'ng, karta to'plamida aynan \(K\) ta karta yolg'on ma'lumot saqlasin.
Birinchi qatorda ikkita butun son \(N\) va \(K\) berilgan \((1 \le N \le 5\cdot10^5, 0 \le K \le N)\).
Keyingi \(N\) qatorning har birida bitta butun son \(a_i\) yozilgan \((0 \le a_i \le 5\cdot10^5)\) — bu \(i-\)chi kartadagi ma'lumot.
Agar masalani yechish mumkin bo‘lmasa, bitta \(−1\) chiqaring. Aks holda, bitta qatorda \(N\) ta kartaning raqamlarini bo‘yicha bo‘shliq bilan ajratib yozing — bu kartalarni yuqoridan pastga qarab qanday tartibda qo‘yish kerakligini ko‘rsatadi. Agar bir nechta yechim bo‘lsa, istalgan bittasini chiqarishingiz mumkin.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 2 1 2 2 3 |
2 3 1 2 |
| 2 |
5 3 2 1 3 0 3 |
3 3 0 1 2 |
| 3 |
6 4 0 2 5 2 0 1 |
-1 |
Ikkinchi test uchun izoh:
Soddalashtirish uchun kartalarni ularning da’volariga qarab rost/soxta deb belgileymiz.
- Beshinchi kartaning ostida 0 ta soxta karta bor, shuning uchun u soxta.
- To‘rtinchi kartaning ostida 1 ta soxta karta bor, shuning uchun u rost.
- Uchinchi kartaning ostida 1 ta soxta karta bor, shuning uchun u rost.
- Ikkinchi kartaning ostida 1 ta soxta karta bor, shuning uchun u soxta.
- Birinchi kartaning ostida 2 ta soxta karta bor, shuning uchun u soxta.
Demak, jami 3 ta soxta karta mavjud.
Telegram kanalimizga obuna bo'ling