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 #include using namespace std; #define int long long using ll = long long; const ll inf = 2e18; const int maxN = 1 << 18; vector _cnt[maxN]; // vector _sums[maxN]; ll get(ll n, ll k) { k = min(k, n * (n - 1) / 2 - k); if(k < 0) return 0; if(n == 1) return k == 0; assert(k >= 0); if(_cnt[n].size() <= k) return inf; return _cnt[n][k]; } ll getsum(ll n, ll a, ll b) { a = max(a, 0LL); b = min(b, n * (n - 1) / 2); if(a > n * (n - 1) / 2) return 0; if(a > b) { printf("%lld %lld %lld\n", n, a, b); assert(a <= b); } if((b - a) > 40) return inf; ll res = 0; for(ll i = a; i <= b; ++i) res = min(inf, res + get(n, i)); return res; } ll count(int n, ll k) { // ll res = 0; // for(int in = 0; in < n; ++in) // res = min(get(n - 1, k - in, _cnt) + res, inf); // return res; return getsum(n - 1, k - n + 1, k); } const int r = 1 << 18; int tree[2 * r]; void print_kth(int k) { int x = 1; tree[x]--; while(x < r) { if(tree[2 * x] >= k) x *= 2; else { x = 2 * x + 1; k -= tree[x - 1]; } tree[x]--; } printf("%lld ", x - r); } void gen(ll n, ll k, ll inw) { if(n == 0) return; assert(inw <= n * (n - 1) / 2); // printf("n=%lld, k=%lld, inw=%lld\n", n, k, inw); ll min_b = max(0LL, inw - (n - 1) * (n - 2) / 2); ll a = min_b - 1, b = min(n - 1, inw), avg; while(b - a > 1) { avg = (a + b) / 2; // printf("%lld %lld\n", a, b); assert(avg >= 0); // printf("sum %lld..%lld=%lld\n", inw-avg, inw, getsum(n-1, inw-avg, avg)); if(getsum(n - 1, inw - avg, inw - min_b) < k) a = avg; else b = avg; } if(b) k -= getsum(n - 1, inw - b + 1, inw - min_b); assert(k > 0); print_kth(b + 1); // printf("!!! [b=%lld]\n", b); gen(n - 1, k, inw - b); } #undef int int main() { #define int long long ll n, k; scanf("%lld%lld", &n, &k); for(ll _n = 1; _n <= n; ++_n) for(ll x, sx = 0, _k = 0; _k <= _n * (_n - 1) / 2; ++_k) { x = count(_n, _k); if(x != inf) { _cnt[_n].push_back(x); // if(_k) sx = _sums[_n].back(); // _sums[_n].push_back(min(inf, sx + x)); } else break; } if((n * (n - 1)) & 3 || count(n, n * (n - 1) / 4) < k) { puts("NIE"); return 0; } puts("TAK"); for(int i = 1; i <= n; ++i) tree[i + r] = 1; for(int i = r - 1; i; --i) tree[i] = tree[2 * i] + tree[2 * i + 1]; gen(n, k, n * (n - 1) / 4); puts(""); }