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
#include <bits/stdc++.h>
using namespace std;
bool testcase_to_380(long long n, long long k, long long inv, long long cur, int c, long long A[])
{
    long long **D;
    D = new long long* [n+1];
    for(int i=0; i<=n; i++)
        D[i] = new long long [inv+1];
    for(int i=0; i<=n; i++)
        for(int j=0; j<=inv; j++)
            D[i][j]=0;
    D[1][0]=1;
    for(int i=2; i<=n; i++){
        //cout << i << ": " <<endl;
        for(int j=0; j<=(i*(i-1)/2) && j<=inv; j++){
            for(int p=1; p<=i && D[i][j]<=k; p++)
                if(j>=p-1)
                    D[i][j]+=D[i-1][j-(p-1)];
            //cout << "  D[" << i << "][" << j << "] = " << D[i][j] <<endl;
        }
    }
    if(D[n][inv]<k){
        cout << "NIE\n";
        return false;
    }
    long long k1=inv, a, ind; long long Value[n+1]; bool Taken[n+1];
    for(int i=0; i<=n; i++)
        Taken[i]=false;
    for(int i=0; i<=n; i++)
        Value[i]=i;
    cur=0;
    for(int e=n; e>=1; e--){
        a=-1;
        for(int i=1; i<=e && a==-1; i++)
            if(cur+D[e-1][k1-(i-1)]>=k)
                a=i, k1-=(i-1);
            else
                cur+=D[e-1][k1-(i-1)];
        if(a==-1)
            a=1;
        //cout << e << " " << a << " " << Value[a] << "  " << cur << " " << k << " " << k1 <<endl;

        A[n-e+c]=Value[a]+c;
        Taken[Value[a]]=true;
        ind=1;
        for(int l=1; l<=n; l++)
            if(!Taken[l])
                Value[ind++]=l;
    }
    return true;
}
bool testcase_over_380(long long n, long long k, long long inv, long long cur, int c, long long A[])
{
    for(int i=0; i<(n/4); i++)
        A[i]=i+1;
    return testcase_to_380(n-(n/4),k,inv,cur,(n/4),A);
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    long long n, k, inv, cur=0;
    cin >> n >> k;
    inv=(n*(n-1)/2);
    if(inv%2!=0){
        cout << "NIE\n";
        return 0;
    }
    long long A[n+1];
    bool good = (n<=380) ? testcase_to_380(n,k,inv/2,cur,0,A) : testcase_over_380(n,k,inv/2,cur,0,A);
    if(good){
        cout << "TAK\n";
        for(int i=0; i<n; i++)
            cout << A[i] << " ";
        cout <<"\n";
    }
    return 0;
}