#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/tag_and_trait.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> set_t; typedef long long ll; const ll inf = 1e18 + 1; const int N = 250001; vector<ll> dp[N]; ll get(ll n, ll k) { if(k < dp[n].size()) return dp[n][k]; k = n * (n - 1) / 2 - k; if(k < 0) return 0; if(k < dp[n].size()) return dp[n][k]; return inf; } int main() { ll n, k; scanf("%lld %lld", &n, &k); dp[0] = { 1LL }; for(int i = 1; i <= n; i++) { long long m = 1LL * i * (i - 1) / 2; for(int j = 0; j <= m; j++) { ll t = 0; for(int k = j; k >= 0 && k > j - i; k--) { t += get(i - 1, k); if(t >= inf) { t = inf; break; } } if(t == inf) break; dp[i].push_back(t); } } if(n * (n - 1) % 4 || get(n, n * (n - 1) / 4) < k) { puts("NIE"); return 0; } ll inv = n * (n - 1) / 4; puts("TAK"); set_t l; for(int i = 1; i <= n; i++) l.insert(i); for(int i = 1; i <= n; i++) { ll nz = (n - i) * (n - i - 1) / 2; for(int j = max(0LL, inv - nz); ; j++) if(get(n - i, inv - j) >= k) { inv -= j; auto it = l.find_by_order(j); printf("%d ", *it); l.erase(it); break; } else k -= get(n - i, inv - j); } puts(""); }
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 | #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/tag_and_trait.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> set_t; typedef long long ll; const ll inf = 1e18 + 1; const int N = 250001; vector<ll> dp[N]; ll get(ll n, ll k) { if(k < dp[n].size()) return dp[n][k]; k = n * (n - 1) / 2 - k; if(k < 0) return 0; if(k < dp[n].size()) return dp[n][k]; return inf; } int main() { ll n, k; scanf("%lld %lld", &n, &k); dp[0] = { 1LL }; for(int i = 1; i <= n; i++) { long long m = 1LL * i * (i - 1) / 2; for(int j = 0; j <= m; j++) { ll t = 0; for(int k = j; k >= 0 && k > j - i; k--) { t += get(i - 1, k); if(t >= inf) { t = inf; break; } } if(t == inf) break; dp[i].push_back(t); } } if(n * (n - 1) % 4 || get(n, n * (n - 1) / 4) < k) { puts("NIE"); return 0; } ll inv = n * (n - 1) / 4; puts("TAK"); set_t l; for(int i = 1; i <= n; i++) l.insert(i); for(int i = 1; i <= n; i++) { ll nz = (n - i) * (n - i - 1) / 2; for(int j = max(0LL, inv - nz); ; j++) if(get(n - i, inv - j) >= k) { inv -= j; auto it = l.find_by_order(j); printf("%d ", *it); l.erase(it); break; } else k -= get(n - i, inv - j); } puts(""); } |