#include<bits/stdc++.h> #define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++) #define all(v) (v).begin(), (v).end() #define SZ(v) (int)((v).size()) #define pb push_back #define ft first #define sd second typedef long long ll; typedef unsigned long long ull; typedef long double ld; const long long INF = 1e18L + 1; const int IINF = 1e9 + 1; using namespace std; template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; } template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...); } #ifdef LOCAL #define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #else #define DBG(...) (__VA_ARGS__) #define cerr if(0)cout #endif #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using ordered_set = tree< T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 250000; vector<vector<ll>> mah(N + 1); ll f(ll n, ll k) { if (n == 0 or k > n * (n - 1) / 2) { return 0; } if (k > n * (n - 1) / 4) { k = n * (n - 1) / 2 - k; } if (k >= SZ(mah[n])) { return INF; } return mah[n][k]; } void prep() { rep (n, 1, N) { mah[n].pb(1); rep (k, 1, n * (n - 1) / 2 + 1) { mah[n].pb(0); for (int i = 0; i < n and k - i >= 0; i++) { ull dod = ((k - i < SZ(mah[n - 1])) ? mah[n - 1][k - i] : 0); mah[n][k] += dod; if (mah[n][k] >= INF) { mah[n][k] = INF; k = n * n; break; } } } } } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif prep(); ll n, k; cin >> n >> k; if (n % 4 != 0 and n % 4 != 1) { cout << "NIE"; return 0; } if (f(n, n * (n - 1) / 4) < k) { cout << "NIE"; return 0; } ordered_set<ll> liczby; rep (i, 0, n) { liczby.insert(i); } vector<ll> wyn(n); ll inv_pref = 0; rep (i, 0, n) { ll tmp = n - i - 1; ll max_non_zero = tmp * (tmp - 1) / 2; ll ind = max(0LL, n * (n - 1) / 4 - inv_pref - max_non_zero); for (auto it = liczby.find_by_order(ind); it != liczby.end(); it++, ind++) { auto x = *it; ll l = n * (n - 1) / 4 - (inv_pref + ind); ll z = f(n - i - 1, l); if (z >= k) { wyn[i] = x; inv_pref += ind; liczby.erase(it); break; } else { k -= z; } } } wyn[n - 1] = *liczby.begin(); cout << "TAK\n"; for (auto x: wyn) { cout << x + 1 << " "; } }
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 | #include<bits/stdc++.h> #define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++) #define all(v) (v).begin(), (v).end() #define SZ(v) (int)((v).size()) #define pb push_back #define ft first #define sd second typedef long long ll; typedef unsigned long long ull; typedef long double ld; const long long INF = 1e18L + 1; const int IINF = 1e9 + 1; using namespace std; template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; } template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...); } #ifdef LOCAL #define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #else #define DBG(...) (__VA_ARGS__) #define cerr if(0)cout #endif #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using ordered_set = tree< T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 250000; vector<vector<ll>> mah(N + 1); ll f(ll n, ll k) { if (n == 0 or k > n * (n - 1) / 2) { return 0; } if (k > n * (n - 1) / 4) { k = n * (n - 1) / 2 - k; } if (k >= SZ(mah[n])) { return INF; } return mah[n][k]; } void prep() { rep (n, 1, N) { mah[n].pb(1); rep (k, 1, n * (n - 1) / 2 + 1) { mah[n].pb(0); for (int i = 0; i < n and k - i >= 0; i++) { ull dod = ((k - i < SZ(mah[n - 1])) ? mah[n - 1][k - i] : 0); mah[n][k] += dod; if (mah[n][k] >= INF) { mah[n][k] = INF; k = n * n; break; } } } } } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif prep(); ll n, k; cin >> n >> k; if (n % 4 != 0 and n % 4 != 1) { cout << "NIE"; return 0; } if (f(n, n * (n - 1) / 4) < k) { cout << "NIE"; return 0; } ordered_set<ll> liczby; rep (i, 0, n) { liczby.insert(i); } vector<ll> wyn(n); ll inv_pref = 0; rep (i, 0, n) { ll tmp = n - i - 1; ll max_non_zero = tmp * (tmp - 1) / 2; ll ind = max(0LL, n * (n - 1) / 4 - inv_pref - max_non_zero); for (auto it = liczby.find_by_order(ind); it != liczby.end(); it++, ind++) { auto x = *it; ll l = n * (n - 1) / 4 - (inv_pref + ind); ll z = f(n - i - 1, l); if (z >= k) { wyn[i] = x; inv_pref += ind; liczby.erase(it); break; } else { k -= z; } } } wyn[n - 1] = *liczby.begin(); cout << "TAK\n"; for (auto x: wyn) { cout << x + 1 << " "; } } |