| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 2 | 1 | 1 | 50.000% |
Permutacją n-elementową nazwiemy taki ciąg liczb naturalnych z zakresu od 1 do n, w którym każda liczba występuje dokładnie raz. Parę jego różnych elementów nazwiemy inwersją, gdy większy z tych elementów występuje w tym ciągu wcześniej.
Interesują nas stabilne permutacje, to znaczy takie, w których liczba inwersji nie zmieni się, jeśli odwrócimy kolejność wszystkich liczb w ciągu. Znajdź k-tą w porządku leksykograficznym stabilną permutację n-elementową.
Pierwszy wiersz wejścia zawiera dwie liczby całkowite n, k (1 ≤ n ≤ 250 000, 1 ≤ k ≤ 1018), oznaczające liczbę elementów permutacji i numer poszukiwanej stabilnej permutacji.
Jeśli istnieje k-ta w porządku leksykograficznym permutacja n-elementowa, wypisz w pierwszym wierszu wejścia słowo TAK, natomiast w drugim wierszu wypisz n liczb naturalnych oddzielonych pojedynczymi odstępami – kolejne elementy szukanej permutacji.
Jeśli zadana permutacja nie istnieje, w jedynym wierszu wyjścia wypisz słowo NIE.
4 3
TAK 2 4 1 3
4 57
NIE
Wyjaśnienie do przykładu: Istnieje 6 stabilnych permutacji 4-elementowych:
(1, 4, 3, 2), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 2, 1, 4), (4, 1, 2, 3).
Contest > Algorithmic Engagements > PA 2017 1-1번