C. Сережа ба Тэмцээн

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сережагийн сүүлийн Кодсекрофийн раундын үеэр сервер хэд хэдэн удаа доголдсон ба раундыг зарим оролцогчдын хувьд үнэлэхгүй байлгахаар шийдсэн.

Тэмцээнд оролцсон $n$ хүмүүсийг авч үзье. Эхний байранд байгаа оролцогч $a_{1}$ үзүүлэлттэй, хоёрдугаар байранд байгаа оролцогч $a_{2}$, $...$, ба $n$-р байранд байгаа оролцогч $a_{n}$ үзүүлэлттэй гэе. Кодсекроф сайт дээрх үзүүлэлтийн өөрчлөлт нь томьёогоор тооцоологддог.

Раунд дууссаны дараа Кодсекрофийн удирдлага оролцогчдын дүнгийн хүснэгтийг нийтлэсэн. Тэд $d_{i} < k$ оролцогчийн хувьд энэ раундад үнэлэгдээгүй байхаар шийдсэн. Гэвч тэд оролцогчдын дүнгийн хүснэгт динамик байхыг олсон үеийн гайхшралыг төсөөлье. Өөрөөр хэлбэл үнэлгээнээс нэг оролцогч хасагдахад тэр дүнгийн хүснэгтээс хасагдах ба үнэлгээ шинэ хүснэгтийн дагуу дахин тооцоологдсон. Ингээд мэдээж үнэлгээнээс хасахад зориулсан бүх мэдээллүүд одоогийн хүснэгтийн харагдац байна.

Үнэлгээнээс хасахад зориулсан бүх мэдээллүүдийн дундаас авч үзэх хамгийн эхний мэдээлэл нь $d_{i} < k$ байх хүмүүсийн хувьд хамгийн шилдэг үзүүлэлттэй оролцогчийнх (хамгийн бага байранд буй) байна гэдгийг бид мэдэж байна. Бид үнэлгээнээс хасагдах мэдээллүүд бүх оролцогчдоор илгээгдсэн байна гэдгийг бас мэднэ.

Одоо Сережа тэмцээний үнэлгээнээс хасагдсан оролцогчдын тоо хэд вэ мөн үнэлгээнээс хасагдсан оролцогчдын анхны хүснэгтэд байсан дугаарууд хэд вэ гэж бодож байна. Бодлогын нөхцлийг илүү сайн ойлгохын тулд эхний жишээний анализыг сайн харна уу.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$, $k$ $(1 ≤ n ≤ 2*10^{5},  - 10^{9} ≤ k ≤ 0)$ байна. Хоёр дахь мөрөнд зайгаар тусгаардагдсан $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{9})$ байх ба анхны хүснэгт дахь оролцогчдын үзүүлэлт байна.

Гаралт

Оролцогчдын дугаарыг тэд хүснэгтээс хасагдсан дарааллаар хэвлэ. Оролцогчдын анхны дугааруудыг хэвлэх буюу оролцогчдын анхны хүснэгтэд байсан дугаар гэсэн үг.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 0
5 3 4 1 2
Гаралт
2
3
4
Оролт
10 -10
5 5 1 7 5 1 2 4 9 2
Гаралт
2
4
5
7
8
9

Тэмдэглэл

Эхний жишээг авч үзье.

  1. Эхэндээ тэмцээнд оролцогчдын үзүүлэлтүүдийн дараалал [5, 3, 4, 1, 2]-тай тэнцүү байсан. Та энэ дарааллыг үзүүлэлтийг өөрчлөх дарааллыг тооцолохдоо ашиглаж чадна: [0, -9, -13, 8, 14]. Бодлогын нөхцлийн дагуу хоёр дахь байрт шалгарсан оролцогчийн мэдээлэл эхнийх гэж тооцогдоно.
  2. Хоёрдугаар байрт шалгарсан оролцогч хасагдсан даруйд шинэ үзүүлэлтүүдийн дараалал [5, 4, 1, 2] болно. Энэ дарааллаар та үзүүлэлтийг өөрчлөх дарааллыг тоолж чадна: [0, -8, 2, 6]. Бодлогын нөхцлийн дагуу хоёр дахь байрт шалгарсан оролцогчийн мэдээллийг авч үзнэ. Анх энэ оролцогч гуравдугаар байрт шалгарсан.
  3. Шинэ үзүүлэлтүүдийн дараалал [5, 1, 2] болох ба шинэ үзүүлэлтийг өөрчлөх дараалал [0, -1, 1] болно. Хоёр дахь байранд буй оролцогчийн мэдээллийг авч үзэх ба анх энэ оролцогч дөрөвдүгээр байрт шалгарсан.
  4. Шинэ үзүүлэлтүүдийн дараалал [5, 2] болох ба шинэ үзүүлэлтийг өөрчлөх дараалал [0, 0] болно. Өөр ямар ч мэдээлэл авч үзэхгүй.

Ингээд та 2, 3, 4 гэж хэвлэх ёстой.

Сэтгэгдлүүдийг ачааллаж байна...