Задача №1841. Нерешаемая задача
Вениамин очень любит придумывать интересные задачки. Собравшиеся на его очередной контест друзья были удивлены: на этот раз им предстояло решить нерешаемую задачку. Все друзья написали какие-то решения, но, естественно, в лимит по времени ни одно из этих решений не укладывалось. Измерение времени на сервере происходит с погрешностью, поэтому составить таблицу результатов оказалось непростой задачей. Немного подумав, Вениамин решил распределить места между друзьями, следуя следующим правилам:
- места в таблице у двух участников должны быть одинаковыми тогда и только тогда, когда разница во времени работы программ этих участников не больше \(k\);
- если, согласно первому правилу, у двух каких-либо участников разные места, более высокое место занимает тот, чья программа работает быстрее.
Каждое место в таблице, меньшее максимального, должно быть занято хотя бы одним участником.
Помогите Вениамину составить таблицу результатов.
В первой строке входного файла содержатся два натуральных числа \(n\) (количество собравшихся на контест друзей) и \(k\) (1 \(\le\) \(n\) \(\le\) 100000, 1 \(\le\) \(k\) \(\le\)2000000000). В следующей строке содержатся \(n\) натуральных чисел \(t_i\) (1 \(\le\) \(t_i\) \(\le\) 2000000000) — времена работы программ.
Если составить таблицу, удовлетворяющую всем условиям, возможно, в первой строке выведите «Yes», а в следующей — \(n\) чисел \(p_i\), каждое из которых означает место в таблице \(i\)-го участника.
Если же составить таблицу нельзя, то в первой строке выведите «No», а во второй и третьей строках выведите соответственно число \(c\) (3 \(\le\) \(c\) \(\le\) \(n\)) и \(c\) чисел \(a_i\) — последовательность различных чисел от 1 до \(n\) со следующими свойствами:
\(\forall i > 1\) \(t_{a_i}\) \(\ge\) \(t_{a_{i−1}}\);
\(\forall i > 1\) \(t_{a_i}\) − \(t_{a_{i-1}}\) \(\le\) \(k\);
\(t_{a_c}\)−\(t_{a_1}\) > \(k\).
5 3 9 4 1 8 3
Yes 2 1 1 2 1
5 3 9 5 1 8 3
No 3 3 5 2