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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 250000
#define KMAX 1000000000000000000ULL
#define ROW_LIM 105
#define NMAX_FULL 21

typedef unsigned long long ull;

struct Node {
    Node *left, *right;
    unsigned val, cnt;
    bool has_val;

    unsigned get(unsigned i);
};

unsigned Node::get(unsigned i)
{
    unsigned less_cnt = left ? left->cnt : 0;

    if (i < less_cnt) {
        --cnt;
        return left->get(i);
    } else if (has_val && i == less_cnt) {
        --cnt;
        has_val = false;
        return val;
    } else if (right) {
        --cnt;
        return right->get(i-less_cnt-has_val);
    } else {
        return 0;
    }
}

Node *make_tree(Node *nodes, unsigned n)
{
    unsigned mid = n/2;
    Node *curr = nodes+mid;

    curr->cnt = 1;
    curr->has_val = true;
    if (mid > 0) {
        curr->left = make_tree(nodes, mid);
        curr->cnt += curr->left->cnt;
    } else {
        curr->left = nullptr;
    }
    if (n > mid+1) {
        curr->right = make_tree(curr+1, n-(mid+1));
        curr->cnt += curr->right->cnt;
    } else {
        curr->right = nullptr;
    }
    return curr;
}

int main()
{
    static ull mahonian[NMAX+1][ROW_LIM+1];
    static unsigned r[NMAX+1];
    static Node nodes[NMAX];
    unsigned n;
    ull k, inv;
    Node *tree;

    scanf("%u%llu", &n, &k);

    inv = (ull)n*(n-1)/4;
    if ((ull)n*(n-1)%4 != 0) {
        puts("NIE");
        return 0;
    }

    mahonian[1][0] = 1;
    for (unsigned i = 1; i < n; ++i) {
        ull s = 0;
        unsigned mmax = min((ull)i*(i+1)/2, (ull)ROW_LIM);

        for (unsigned j = 0; j <= min(mmax, i); ++j) {
            s += mahonian[i][j];
            s = min(s, KMAX+1);
            mahonian[i+1][j] = s;
        }
        for (unsigned j = i+1; j <= mmax; ++j) {
            s += mahonian[i][j];
            s -= mahonian[i][j-i-1];
            s = min(s, KMAX+1);
            mahonian[i+1][j] = s;
        }
    }
    if (n <= NMAX_FULL && k > mahonian[n][inv]) {
        puts("NIE");
        return 0;
    }

    for (unsigned i = n; i > 1; --i) {
        ull mmax = (ull)(i-1)*(i-2)/2;

        while (inv > mmax) {
            --inv;
            ++r[i];
        }
        for (;;) {
            unsigned m;
            ull mahonian_val;

            m = min(min(inv, mmax-inv), (ull)ROW_LIM);
            mahonian_val = mahonian[i-1][m];
            if (k <= mahonian_val) {
                break;
            }
            k -= mahonian_val;
            --inv;
            ++r[i];
        }
    }

    for (unsigned i = 0; i < n; ++i) {
        nodes[i].val = i+1;
    }
    tree = make_tree(nodes, n);

    puts("TAK");
    for (unsigned i = n; i > 0; --i) {
        printf("%u ", tree->get(r[i]));
    }
    putchar('\n');

    return 0;
}