#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/trie_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; const ll infty = (ll)(3e18) + 5; const int N = 250005; vector<ll> dp[N]; ll f(ll n, ll k) { if (k < 0 || k > n*(n-1)/2LL) return 0; if (k < (ll) dp[n].size()) return dp[n][k]; if (n*(n-1)/2LL - k < (ll) dp[n].size()) return dp[n][n*(n-1)/2LL - k]; return infty; } int main() { dp[0].push_back(1); for (int n = 1; n < N; n++) { dp[n].reserve(10); dp[n].push_back(1); for (ll k = 1; k <= 1LL*n*(n-1)/2LL; k++) { ll val = 0; for (ll i = max(0LL, k-n+1); i <= k; i++) { val += f(n-1,i); if (val >= infty) { val = infty; break; } } dp[n].push_back(val); if (dp[n].back() >= infty) break; } } ll n; ll kta; scanf("%lld%lld", &n, &kta); if (n * (n-1) % 4LL != 0) { puts("NIE"); return 0; } if (f(n,n*(n-1)/4LL) < kta) { puts("NIE"); return 0; } printf("TAK\n"); tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> S; for (int i = 1; i <= n; i++) S.insert(i); ll k = n * (n-1) / 4LL; for (int i = 1; i <= n; i++) { ll nn = n - i + 1; for (int co = max(1LL, k+1-(nn-1)*(nn-2)/2LL); co <= nn; co++) { ll xd = f(nn-1, k-co+1); if (xd >= kta) { auto xdd = S.find_by_order(co-1); printf("%d ", *xdd); S.erase(xdd); k = k-co+1; break; } else kta -= xd; } } printf("\n"); 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 | #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/trie_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; const ll infty = (ll)(3e18) + 5; const int N = 250005; vector<ll> dp[N]; ll f(ll n, ll k) { if (k < 0 || k > n*(n-1)/2LL) return 0; if (k < (ll) dp[n].size()) return dp[n][k]; if (n*(n-1)/2LL - k < (ll) dp[n].size()) return dp[n][n*(n-1)/2LL - k]; return infty; } int main() { dp[0].push_back(1); for (int n = 1; n < N; n++) { dp[n].reserve(10); dp[n].push_back(1); for (ll k = 1; k <= 1LL*n*(n-1)/2LL; k++) { ll val = 0; for (ll i = max(0LL, k-n+1); i <= k; i++) { val += f(n-1,i); if (val >= infty) { val = infty; break; } } dp[n].push_back(val); if (dp[n].back() >= infty) break; } } ll n; ll kta; scanf("%lld%lld", &n, &kta); if (n * (n-1) % 4LL != 0) { puts("NIE"); return 0; } if (f(n,n*(n-1)/4LL) < kta) { puts("NIE"); return 0; } printf("TAK\n"); tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> S; for (int i = 1; i <= n; i++) S.insert(i); ll k = n * (n-1) / 4LL; for (int i = 1; i <= n; i++) { ll nn = n - i + 1; for (int co = max(1LL, k+1-(nn-1)*(nn-2)/2LL); co <= nn; co++) { ll xd = f(nn-1, k-co+1); if (xd >= kta) { auto xdd = S.find_by_order(co-1); printf("%d ", *xdd); S.erase(xdd); k = k-co+1; break; } else kta -= xd; } } printf("\n"); return 0; } |