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
117
118
119
120
121
122 | #include<cstdio>
#include<iostream>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<iomanip>
#include<fstream>
#include<ctime>
#include<climits>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const LL INFLL = 1000000000000000001LL;
const int MA = 250005;
const int MB = 530000;
vector<LL> wek[MA + 5];
int i, j, l, tab[MA], n, c, a, w[MB], M;
LL res, add, b, k, sum, maxx;
bool overf;
int getAndErase(int e) {
int v = 1;
while (v <= M) {
w[v]--;
if (w[2 * v] >= e) v *= 2; else {
e -= w[2 * v];
v = v * 2 + 1;
}
}
w[v]--;
return v - M;
}
void init (int a) {
int i;
M=1;
while (M<a) M*=2;
for (i=1;i<2*M;i++) w[i] = 0;
M--;
for (i=1;i<=a;i++) w[M + i] = 1;
for (i=M;i>=1;i--) w[i] = w[2 * i] + w[2 * i + 1];
}
LL get(int a, LL b) {
if (b < wek[a].size()) return wek[a][b];
LL otB = a * 1LL * (a - 1) / 2 - b;
if (otB < wek[a].size()) return wek[a][otB];
return INFLL;
}
int main() {
cin >> n >> k;
b = n * 1LL * (n - 1) / 2;
if (b % 2 == 1) {
printf("NIE\n");
return 0;
}
b /= 2;
wek[1].pb(1);
for (i=2;i<=n;i++) {
overf = false;
for (j=0;j<=i*1LL*(i-1)/2;j++) {
res = 0;
for (l=0;l<i && l<=j;l++) {
add = (j - l >= wek[i - 1].size()) ? 0 : wek[i - 1][j - l];
if (res + add >= INFLL) {
overf = true;
break;
}
res += add;
}
if (overf) {
wek[i].pb(INFLL);
break;
}
wek[i].pb(res);
}
}
if (b < wek[n].size() && wek[n][b] < k) {
printf("NIE\n");
return 0;
}
init(n);
a = n;
while (a > 1) {
//cout << a << " " << b << " " << k << endl;
sum = 0;
c = 0;
maxx = (a - 1) * 1LL * (a - 2) / 2;
if (b > maxx) {
c += (b - maxx);
b = maxx;
}
while (true) {
add = get(a - 1, b);
if (sum + add >= k) {
break;
}
sum += add;
c++;
b--;
}
tab[n - a] = getAndErase(c + 1);
a--;
k-=sum;
}
tab[n - 1] = getAndErase(1);
printf("TAK\n");
for (i=0;i<n;i++) printf("%d ", tab[i]);
printf("\n");
//for (i=0;i<n - 1;i++) if (tab[i] > tab[i+1]) printf("%d\n", i);
}
|