#include <bits/stdc++.h> using namespace std; const int N = 250005, BASE = 262144; int tree[2 * BASE + 1]; int n; long long K; vector<long long> dp[N]; long long calcInverse(int n) { return (long long)n * (n - 1) / 2; } void remove(int pos) { pos += BASE; while (pos >= 1) { tree[pos]--; pos /= 2; } } int query(int pos, int value) { if (pos >= BASE) { return pos - BASE; } if (tree[2 * pos] >= value) { return query(2 * pos, value); } else { return query(2 * pos + 1, value - tree[2 * pos]); } } void add(long long &w, int x, long long y) { y = min(y, calcInverse(x) - y); if (y >= 0 && y < (long long)dp[x].size()) { w += dp[x][y]; } else if (y >= (long long)dp[x].size() && y <= calcInverse(x) / 2) { w = K; } } int main() { scanf("%d %lld", &n, &K); dp[0].push_back(1LL); for (int i = 1; i <= n; i++) { long long prefInv = calcInverse(i); for (long long j = 0; j <= prefInv / 2; j++) { long long tmp = 0; for (int k = 0; k < i && j - k >= 0; k++) { add(tmp, i - 1, j - k); if (tmp >= K) { break; } } if (tmp >= K) { break; } dp[i].push_back(tmp); } } if (calcInverse(n) % 2 != 0 || (calcInverse(n) / 2 < (long long)dp[n].size() && dp[n][calcInverse(n) / 2] < K)) { printf("NIE\n"); return 0; } for (int i = 1; i <= n; i++) { tree[i + BASE] = 1; } for (int i = BASE - 1; i >= 1; i--) { tree[i] = tree[2 * i] + tree[2 * i + 1]; } printf("TAK\n"); long long inv = calcInverse(n) / 2; for (int i = n; i >= 1; i--) { long long prevInv = calcInverse(i - 1); long long start = max(0LL, inv - prevInv); for (long long j = start; j < i; j++) { long long remainingInv = inv - j; remainingInv = min(remainingInv, prevInv - remainingInv); if ((long long)dp[i - 1].size() <= remainingInv || dp[i - 1][remainingInv] >= K) { int nextElement = query(1, j + 1); printf("%d ", nextElement); remove(nextElement); inv -= j; break; } K -= dp[i - 1][remainingInv]; } } return 0; }
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 | #include <bits/stdc++.h> using namespace std; const int N = 250005, BASE = 262144; int tree[2 * BASE + 1]; int n; long long K; vector<long long> dp[N]; long long calcInverse(int n) { return (long long)n * (n - 1) / 2; } void remove(int pos) { pos += BASE; while (pos >= 1) { tree[pos]--; pos /= 2; } } int query(int pos, int value) { if (pos >= BASE) { return pos - BASE; } if (tree[2 * pos] >= value) { return query(2 * pos, value); } else { return query(2 * pos + 1, value - tree[2 * pos]); } } void add(long long &w, int x, long long y) { y = min(y, calcInverse(x) - y); if (y >= 0 && y < (long long)dp[x].size()) { w += dp[x][y]; } else if (y >= (long long)dp[x].size() && y <= calcInverse(x) / 2) { w = K; } } int main() { scanf("%d %lld", &n, &K); dp[0].push_back(1LL); for (int i = 1; i <= n; i++) { long long prefInv = calcInverse(i); for (long long j = 0; j <= prefInv / 2; j++) { long long tmp = 0; for (int k = 0; k < i && j - k >= 0; k++) { add(tmp, i - 1, j - k); if (tmp >= K) { break; } } if (tmp >= K) { break; } dp[i].push_back(tmp); } } if (calcInverse(n) % 2 != 0 || (calcInverse(n) / 2 < (long long)dp[n].size() && dp[n][calcInverse(n) / 2] < K)) { printf("NIE\n"); return 0; } for (int i = 1; i <= n; i++) { tree[i + BASE] = 1; } for (int i = BASE - 1; i >= 1; i--) { tree[i] = tree[2 * i] + tree[2 * i + 1]; } printf("TAK\n"); long long inv = calcInverse(n) / 2; for (int i = n; i >= 1; i--) { long long prevInv = calcInverse(i - 1); long long start = max(0LL, inv - prevInv); for (long long j = start; j < i; j++) { long long remainingInv = inv - j; remainingInv = min(remainingInv, prevInv - remainingInv); if ((long long)dp[i - 1].size() <= remainingInv || dp[i - 1][remainingInv] >= K) { int nextElement = query(1, j + 1); printf("%d ", nextElement); remove(nextElement); inv -= j; break; } K -= dp[i - 1][remainingInv]; } } return 0; } |