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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const int MAXN=1e6+5;
int tab[MAXN];
map <pair<int,ll>,ll> dp;
map <pair<int,ll>,ll> sum;
const ll inf=1e18;
ordered_set s;

void init(ll n){
	for(int i=1;i<=n;i++)
		dp[{i,0}]=1;
    for(int i=1;i<=n;i++){
		ll x=1LL*i*(i-1)/2;
		ll z=1;
		for(ll j=1;j<=x;j++){
			z=z+dp[{i-1,j}]-(j-i>=0 ? dp[{i-1,j-i}] : 0);
			if(z>inf){
				dp[{i,j}]=inf;
				break;
			}
			dp[{i,j}]=z;
		}
	}
	for(int i=1;i<=n;i++)
		s.insert(i);
}

void solve(ll n,ll k,ll l){
	if(n==0) return;
	if(l==0){
		for(int i=1;i<=n;i++){
			auto x=s.begin();
			s.erase(x);
			cout << *x << ' ';
		}
		return;
	}
	ll sum=0;
	ll y;
	if(n==2) y=0;
	else y=(n-1)*(n-2)/2;
	ll m=l;
	int t=-1;
	if(m>y/2) m=y-l,t=1;
	ll i=1;
	if(m<0){
		i+=-m;
		m=0;
	}
	for(;i<=n;i++,m+=t){
		ll z=dp[{n-1,m}];
		ll a=(z==0 && m>0 && n-1!=0 ? inf : z);
		sum+=a;
		if(sum>=k){
			auto x=s.find_by_order(i-1);
			s.erase(x);
			cout << *x << ' ';
			solve(n-1,k-sum+a,l+1-i);
			return;
		}
	}
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	ll n,k;
    cin >> n >> k;
    init(n);
    if(n==1 && k==1) cout << 1;
    else if((n*(n-1))%4 || k>(dp[{n,n*(n-1)/4}]==0 ? inf : dp[{n,n*(n-1)/4}]))
		cout << "NIE";
	else {
		cout << "TAK\n";
		solve(n,k,n*(n-1)/4);
	}
}