Задача №115149. Манхэттенские перестановки
Пусть есть некоторая перестановка \(p\) длины \(n\). Назовем манхэттенской величиной перестановки число, равное \(|p_1 - 1| + |p_2 - 2| + |p_3 - 3| + |p_4 - 4| + \ldots + |p_n - n|\).
Например, для перестановки \([1, 2, 3]\) манхэттенская величина равна \(|1 - 1| + |2 - 2| + |3 - 3| = 0\), а для перестановки \([3, 1, 2]\) манхэттенская величина равна \(|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4\).
Вам даны \(n\) и \(k\). Найдите такую перестановку \(p\) длины \(n\), что её манхэттенская величина равна \(k\) или скажите, что такой перестановки не существует.
Напомним, что перестановкой длины \(n\) называется массив длины \(n\), в котором каждое число от \(1\) до \(n\) встречается один раз.
Единственная строка входных данных содержит два целых числа \(n\) и \(k\) (\(1 \le n \le 2 \cdot 10^{5}\), \(0 \le k \le 10^{12}\)) — длина перестановки и необходимая манхэттенская величина, соответственно.
Если не существует перестановки длины \(n\), что ее манхэттенская величина равна \(k\), выведите «No». В противном случае выведите «Yes», а после в следующей строке \(n\) различных чисел через пробел — перестановку.
Если существует несколько решений, то выведите любое из них.
В первом примере перестановка \(3, 1, 2\) подходит: \(|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4\).
Во втором примере можно показать, что не существует перестановки длины \(112\) с манхэттенской величиной \(777\).
В третьем примере подходит перестановка \(2, 1, 3, 4, 5\): \(|2-1|+|1-2|+|3 - 3|+|4 - 4|+|5-5|=2\).
В данной задаче \(20\) тестов, помимо тестов из условия, каждый из них оценивается в \(5\) баллов.
Решения, корректно работающие для \(n \le 7\), наберут не менее \(20\) баллов.
Решения, корректно работающие для \(n \le 2000\), наберут не менее \(60\) баллов. Решения, которые выводят «No» на всех тестах, кроме, возможно, тестов из условия, или не находят верный ответ ни на один оцениваемый тест, в котром ответ существует, будут оцениваться в \(0\) баллов.
3 4
Yes 3 2 1
112 777
No
5 2
Yes 2 1 3 4 5
1 1000000000000
No