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 123 124 125 126 127 128 129 130 131 132 133 134 135 #include #include using namespace std; #define NMAX 250000 #define KMAX 1000000000000000000ULL #define ROW_LIM 105 #define NMAX_FULL 21 typedef unsigned long long ull; struct Node { Node *left, *right; unsigned val, cnt; bool has_val; unsigned get(unsigned i); }; unsigned Node::get(unsigned i) { unsigned less_cnt = left ? left->cnt : 0; if (i < less_cnt) { --cnt; return left->get(i); } else if (has_val && i == less_cnt) { --cnt; has_val = false; return val; } else if (right) { --cnt; return right->get(i-less_cnt-has_val); } else { return 0; } } Node *make_tree(Node *nodes, unsigned n) { unsigned mid = n/2; Node *curr = nodes+mid; curr->cnt = 1; curr->has_val = true; if (mid > 0) { curr->left = make_tree(nodes, mid); curr->cnt += curr->left->cnt; } else { curr->left = nullptr; } if (n > mid+1) { curr->right = make_tree(curr+1, n-(mid+1)); curr->cnt += curr->right->cnt; } else { curr->right = nullptr; } return curr; } int main() { static ull mahonian[NMAX+1][ROW_LIM+1]; static unsigned r[NMAX+1]; static Node nodes[NMAX]; unsigned n; ull k, inv; Node *tree; scanf("%u%llu", &n, &k); inv = (ull)n*(n-1)/4; if ((ull)n*(n-1)%4 != 0) { puts("NIE"); return 0; } mahonian[1][0] = 1; for (unsigned i = 1; i < n; ++i) { ull s = 0; unsigned mmax = min((ull)i*(i+1)/2, (ull)ROW_LIM); for (unsigned j = 0; j <= min(mmax, i); ++j) { s += mahonian[i][j]; s = min(s, KMAX+1); mahonian[i+1][j] = s; } for (unsigned j = i+1; j <= mmax; ++j) { s += mahonian[i][j]; s -= mahonian[i][j-i-1]; s = min(s, KMAX+1); mahonian[i+1][j] = s; } } if (n <= NMAX_FULL && k > mahonian[n][inv]) { puts("NIE"); return 0; } for (unsigned i = n; i > 1; --i) { ull mmax = (ull)(i-1)*(i-2)/2; while (inv > mmax) { --inv; ++r[i]; } for (;;) { unsigned m; ull mahonian_val; m = min(min(inv, mmax-inv), (ull)ROW_LIM); mahonian_val = mahonian[i-1][m]; if (k <= mahonian_val) { break; } k -= mahonian_val; --inv; ++r[i]; } } for (unsigned i = 0; i < n; ++i) { nodes[i].val = i+1; } tree = make_tree(nodes, n); puts("TAK"); for (unsigned i = n; i > 0; --i) { printf("%u ", tree->get(r[i])); } putchar('\n'); return 0; }