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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;

#define MAXN 250000

typedef vector<int> vi;
typedef long long ll;

int inv[MAXN];

long long f(int n, ll rank, ll invs){
    static unordered_map<ll,ll> cache[MAXN];
    if(invs < 0 || invs > (ll)n*(n+1)/2) return 0;
    if(n == 0) return 1;
    const auto it = cache[n].find(invs);
    if(it != cache[n].end() && it->second < rank)
        return it->second;
    ll acc=0;
    int up = min<ll>(n, invs);
    int down = max<ll>(0, invs - (ll)n*(n-1)/2);
    for(int i=down;i<=up;++i){
        acc += f(n-1, rank-acc, invs-i);
        if(acc == rank){
            inv[n] = i;
            return rank;
        }
    }
    return cache[n][invs] = acc;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    ll k;
    cin>>n>>k;
    if(n%4 != 0 && (n-1)%4 != 0){
        cout<<"NIE\n";
        return 0;
    }
    ll invs = (ll)n*(n-1)/4;
    int start = (3 + sqrt(2LL*n*n-2*n+1))/2;
    for(int i=max(start-2,0);i<n;++i){
        if(f(i,k,invs) == k){
            vi v(n);
            for(int i=0;i<n;++i) v[i]=i+1;
            ordered_set s(v.begin(), v.end());
            cout<<"TAK\n";
            for(int i=n-1;i>=0;--i){
                auto it = s.find_by_order(inv[i]);
                cout<<*it<<' ';
                s.erase(it);
            }
            cout<<'\n';
            return 0;
        }
    }
    cout<<"NIE\n";
    return 0;
}