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
#include<bits/stdc++.h>

using namespace std;

int N, sz[250009];
long long INF = 1e18, K, *dp[250009];

namespace brute {
    int N, p[20];
    void solve ()
    {
        scanf ("%d", &N);
        for (int i=1; i<=N; i++)
            p[i] = i;
        do {
            int cnt = 0;
            for (int i=1; i<=N; i++)
                for (int j=i+1; j<=N; j++)
                    cnt += (p[i] > p[j]);
            if (cnt + cnt == N * (N - 1) / 2)
                for (int i=1; i<=N; i++)
                    printf ("%d%c", p[i], " \n"[i == N]);
        }while (next_permutation (p + 1, p + N + 1));
    }
}

long long getDp (int i, int j)
{
    if (j > 1LL * i * (i - 1) / 2) return 0;
    if (j <= sz[i]) return dp[i][j];
    if (1LL * i * (i - 1) / 2 - j <= sz[i]) return dp[i][i * (i - 1) / 2 - j];
    return INF + 1;
}

void buildDp (int N)
{
    dp[0] = new long long[1], dp[0][0] = 1, sz[0] = 0;
    for (int i=1; i<=N; i++)
    {
        vector < long long > curr;
        for (int j=0; j<=1LL * i * (i - 1) / 2; j++)
        {
            long long val = 0;
            val = 0;
            for (int k=0; k<i && k<=j; k++)
            {
                val += getDp (i - 1, j - k);
                if (val > INF)
                {
                    val = INF + 1;
                    break;
                }
            }
            if (val <= INF) sz[i] = j;
            else break;
            curr.push_back (val);
        }
        dp[i] = new long long[sz[i] + 1];
        for (int j=0; j<=sz[i]; j++)
            dp[i][j] = curr[j];
    }
}

int Size;bool isInside[250009];priority_queue < int > grtst, smlst;
void add (int x){if (isInside[x]) return ; Size ++;
grtst.push (x), smlst.push (-x), isInside[x] = 1;}
void del (int x) {Size -= isInside[x]; isInside[x] = 0;}
int getSmall (){while (!smlst.empty ()){int curr = -smlst.top ();
smlst.pop ();if (isInside[curr]) {del (curr);return curr;}}return -1;}
int getLarge (){while (!grtst.empty ()){int curr = grtst.top ();
grtst.pop ();if (isInside[curr]) {del (curr);return curr;}}return -1;}

void solve (long long val, long long cnt)
{
    int L = Size;
    if (L == 0) return ;
    vector < int > soFar;
    int pos = 1, curr;
    while (1)
    {
        curr = getSmall ();
        if (val <= getDp (L - 1, cnt - (pos - 1)))
            break;
        else
            val -= getDp (L - 1, cnt - (pos - 1));
        soFar.push_back (curr), pos ++;
    }
    printf ("%d ", curr);
    for (auto it : soFar) add (it);
    solve (val, cnt - (pos - 1));
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %lld", &N, &K);
if (N % 4 == 2 || N % 4 == 3)
{
    printf ("NIE\n");
    return 0;
}
buildDp (N);
if (N <= 50 && getDp (N, N * (N - 1) / 4) < K)
{
    printf ("NIE\n");
    return 0;
}
printf ("TAK\n");
for (int i=1; i<=N; i++)
    add (i);
solve (K, 1LL * N * (N - 1) / 4);
printf ("\n");
return 0;
}