#include <bits/stdc++.h> #define int unsigned long long using namespace std; const int MAXN = 250000 + 10; const int INF = 1000000LL * 1000000LL * 1000000LL + 1; const int SIZ = 1<<19; int dp[MAXN][100]; // http://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/ int get_dp(int n, int k) { if (k > n*(n-1)/2) return 0; if (n == 0) { if (k == 0) return 1; return 0; } if (k == 0) return 1; //cerr << "A " << n << " " << k << "\n"; k = min(k, n*(n-1)/2 - k); if (k > 99) { return INF; } if (n > 70 && k > 20) return INF; if (dp[n][k]) return dp[n][k]; int res = 0; for (int i = 0; i <= min(k, n-1); i++) { res += get_dp(n-1, k-i); if (res >= INF) { res = INF; break; } } dp[n][k] = res; if (res == INF) { for (int i = k + 1; i < 100 && dp[n][i] != INF; i++) { dp[n][i] = INF; } } return res; } int t[2*SIZ]; void add(int x, int v = 1) { x += SIZ; while (x > 0) { t[x] += v; x /= 2; } } int sum(int x, int y) { x += SIZ; y += SIZ; int res = t[x]; if (x != y) res += t[y]; while (x/2 != y/2) { if (x%2 == 0) res += t[x+1]; if (y%2 == 1) res += t[y-1]; x/=2; y/=2; } return res; } int fi2(int k, int v = 1) { if (v >= SIZ) return v - SIZ; if (k > t[2*v]) return fi2(k - t[2*v], 2*v + 1); else return fi2(k, 2*v); } int fi(int x) { int p = x; int q = SIZ - 3; while (q-p>1) { int s = (p+q)/2; int r = s - sum(0, s); if (r < x) { p = s + 1; } else { q = s; } } for (int i = p; i <= p+1; i++) if (i - sum(0, i) == x) return i; return -1; } #undef int int main() { #define int unsigned long long int n, k; cin >> n >> k; for (int i = 0; i < 100; i++) get_dp(n, i); vector<int> res; vector<int> used(n+1); int invs = 0; int invstogo = n*(n-1)/4; if (4*invstogo != n*(n-1)) { cout << "NIE\n"; return 0; } if (k > get_dp(n, invstogo)) { cout << "NIE\n"; return 0; } int skipped = 0; for (int i = 1; i <= n; i++) { add(i); } for (int i = 0; i < n; i++) { //cerr << n - i - 1 << "\n"; int lft = n-i-1; //invstogo - invs - good + 1 <= lft*(lft-1)/2 + 100 //good >= invstogo - invs + 1 - lft*(lft-1)/2 - 100 int mgc = lft > 1000 && invstogo > invs + 10 + lft*(lft-1)/2 ? invstogo - invs -10-lft*(lft-1)/2 : 1; for (int j = max(1ULL, mgc); j <= n; j++) { int invs2 = invs; int z = j - 1; invs2 += z; int skipped2 = skipped + get_dp(n-i-1, invstogo-invs2); if (skipped2 >= k) { int jj = fi2(j); res.push_back(jj); used[jj] = 1; add(jj, -1); invs = invs2; break; } else { skipped = skipped2; } } } cout << "TAK\n"; for (auto x: res) cout << x << " "; cout << "\n"; }
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 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 | #include <bits/stdc++.h> #define int unsigned long long using namespace std; const int MAXN = 250000 + 10; const int INF = 1000000LL * 1000000LL * 1000000LL + 1; const int SIZ = 1<<19; int dp[MAXN][100]; // http://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/ int get_dp(int n, int k) { if (k > n*(n-1)/2) return 0; if (n == 0) { if (k == 0) return 1; return 0; } if (k == 0) return 1; //cerr << "A " << n << " " << k << "\n"; k = min(k, n*(n-1)/2 - k); if (k > 99) { return INF; } if (n > 70 && k > 20) return INF; if (dp[n][k]) return dp[n][k]; int res = 0; for (int i = 0; i <= min(k, n-1); i++) { res += get_dp(n-1, k-i); if (res >= INF) { res = INF; break; } } dp[n][k] = res; if (res == INF) { for (int i = k + 1; i < 100 && dp[n][i] != INF; i++) { dp[n][i] = INF; } } return res; } int t[2*SIZ]; void add(int x, int v = 1) { x += SIZ; while (x > 0) { t[x] += v; x /= 2; } } int sum(int x, int y) { x += SIZ; y += SIZ; int res = t[x]; if (x != y) res += t[y]; while (x/2 != y/2) { if (x%2 == 0) res += t[x+1]; if (y%2 == 1) res += t[y-1]; x/=2; y/=2; } return res; } int fi2(int k, int v = 1) { if (v >= SIZ) return v - SIZ; if (k > t[2*v]) return fi2(k - t[2*v], 2*v + 1); else return fi2(k, 2*v); } int fi(int x) { int p = x; int q = SIZ - 3; while (q-p>1) { int s = (p+q)/2; int r = s - sum(0, s); if (r < x) { p = s + 1; } else { q = s; } } for (int i = p; i <= p+1; i++) if (i - sum(0, i) == x) return i; return -1; } #undef int int main() { #define int unsigned long long int n, k; cin >> n >> k; for (int i = 0; i < 100; i++) get_dp(n, i); vector<int> res; vector<int> used(n+1); int invs = 0; int invstogo = n*(n-1)/4; if (4*invstogo != n*(n-1)) { cout << "NIE\n"; return 0; } if (k > get_dp(n, invstogo)) { cout << "NIE\n"; return 0; } int skipped = 0; for (int i = 1; i <= n; i++) { add(i); } for (int i = 0; i < n; i++) { //cerr << n - i - 1 << "\n"; int lft = n-i-1; //invstogo - invs - good + 1 <= lft*(lft-1)/2 + 100 //good >= invstogo - invs + 1 - lft*(lft-1)/2 - 100 int mgc = lft > 1000 && invstogo > invs + 10 + lft*(lft-1)/2 ? invstogo - invs -10-lft*(lft-1)/2 : 1; for (int j = max(1ULL, mgc); j <= n; j++) { int invs2 = invs; int z = j - 1; invs2 += z; int skipped2 = skipped + get_dp(n-i-1, invstogo-invs2); if (skipped2 >= k) { int jj = fi2(j); res.push_back(jj); used[jj] = 1; add(jj, -1); invs = invs2; break; } else { skipped = skipped2; } } } cout << "TAK\n"; for (auto x: res) cout << x << " "; cout << "\n"; } |