1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cmath>

#define LL long long
#define MAX_SIZE 250010

using namespace std;

LL get_max_inversions_count(int n) {
    LL max_inv = 0;
    for (LL i = 0; i < n; i++) {
        max_inv += i;
    }
    return max_inv;
}

LL get_permutations_count(int n, LL inv) {
    LL max_inv, count = 0,  value;
    int m;
    if (inv == 0) {
        if (n < 2)
            return 0LL;
        return 1LL;
    }
    max_inv = get_max_inversions_count(n);
    if (inv > max_inv || max_inv == 0)
        return 0LL;
    if (inv == max_inv)
        return 1LL;
    m = n - 1;

    for (LL i = max(0LL, inv-m); i <= inv; i++) {
        value = get_permutations_count(m, i);
        count += value;
    }
    return count;
}

void select_item(int pos, int n, LL k, LL inv, int *result) {
    LL start = 0, max_perms, added_inv = 0;
    int m = n - pos - 1;

    for (int i = pos; i < n; i++ ) {
        max_perms = get_permutations_count(m, inv);
        if (k <= max_perms || inv == 0) {
            for (int j = i; j > pos; j--) {
                swap(result[j-1], result[j]);
            }
            if (pos < n - 1)
                select_item(pos+1, n, k, inv, result);
            break;
        }
        inv--;
        k -= max_perms;
    }
}

int main()
{
    int n, result[MAX_SIZE];
    LL k, inv, max_inv, stable_inv;

    cin >> n >> k;

    max_inv = get_max_inversions_count(n);

    if (max_inv % 2 == 1) {
        cout << "NIE" << endl;
        return 0;
    }

    inv = max_inv / 2;

    stable_inv = get_permutations_count(n, inv);

    if (k > stable_inv) {
        cout << "NIE" << endl;
        return 0;
    }

    cout << "TAK" << endl;

    for (int i = 0; i < n; i++)
        result[i] = i + 1;
    select_item(0, n, k, inv, result);

    for (int i = 0; i < n; i++)
        cout << result[i] << " ";
    cout << endl;

    return 0;
}