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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

long long n, k, x, inwersje;
long long pom[250005];
int ktory[250005];
int drzewo[525000];
int drz;

vector <long long> v[250005];

int main()
{
	long long MAX = 1000000000000000000LL;
	drz = 262144;
	scanf("%lld%lld", &n, &k);
	if (n % 4 > 1)
	{
		printf("NIE\n");
		return 0;
	}
	v[0].push_back(1);
	for (long long i = 0; i <= n; ++i) pom[i] = i * (i - 1) / 2;
	for (long long i = 1; i <= n; ++i)
	{
		for (long long j = 0; j <= pom[i]; ++j)
		{
			x = 0;
			for (long long k = 0; k < i && k <= j; ++k)
			{
				if (j - k <= pom[i - 1]) x += v[i - 1][j - k];
				if (x > MAX) break;
			}
			if (x > MAX)
			{
				v[i].push_back(MAX + 1);
				break;
			}
			v[i].push_back(x);
		}
	}
	if (n <= 20 && v[n][n * (n - 1) / 4] < k)
	{
		printf("NIE\n");
		return 0;
	}
	inwersje = pom[n] / 2;
	printf("TAK\n");
	for (int j = drz + 1; j <= drz + n; ++j) drzewo[j] = 1;
	for (int j = drz - 1; j > 0; --j) drzewo[j] = drzewo[2 * j] + drzewo[2 * j + 1];
	for (int i = n - 1; i >= 0; --i)
	{
		if (inwersje > pom[i])
		{
			ktory[i] = (int)(inwersje - pom[i]);
			inwersje = pom[i];
		}
		while (ktory[i] < i)
		{
			if (inwersje == 0) break;
			x = min(inwersje, pom[i] - inwersje);
			if (v[i].size() <= x) break;
			if (v[i][x] >= k) break;
			inwersje--;
			k -= v[i][x];
			ktory[i]++;
		}
		ktory[i]++;
		x = 1;
		while (x < drz)
		{
			if (drzewo[2 * x] >= ktory[i]) x *= 2;
			else
			{
				ktory[i] -= drzewo[2 * x];
				x = 2 * x + 1;
			}
		}
		printf("%d ", x - drz);
		while (x > 0)
		{
			drzewo[x]--;
			x /= 2;
		}
	}
	return 0;
}