#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <set> typedef long long ll; const int N = 2.5e5 + 5; const ll inf = 1ll << 60; using namespace std; vector<ll> dp[N]; set<int> num; ll size[N], k; int n; ll count(int n, ll k) { if (k < 0 || k > size[n]) return 0; k = min(k, (ll)size[n] - k); if (k >= dp[n].size()) return inf + inf; else return dp[n][k]; } int main() { scanf("%d%lld", &n, &k); for (int i = 1; i <= n; i++) { size[i] = (ll)i * (i - 1) / 2; } dp[0]= dp[1] = vector<ll> {1}; for (int i = 2; i <= n; i++) { ll tmp = 0; for (int j = 0; j <= size[i]; j++) { tmp += count(i - 1, j) - count(i - 1, j - i); if (tmp > inf) break; dp[i].push_back(tmp); } } if (size[n] % 2 != 0 || count(n, size[n] / 2) < k) { puts("NIE"); return 0; } puts("TAK"); ll m = size[n] / 2; for (int i = 1; i <= n; i++) num.insert(i); for (int i = n - 1; i >= 0; i--) { ll rem = size[i]; for (int j = max(0ll, m - rem); j <= i; j++) { ll tmp = count(i, m - j); if (tmp < k) k -= tmp; else { m -= j; auto it = num.begin(); if (2 * j < i + 1) { for (int k = 0; k < j; k++) ++it; } else { it = num.end(); for (int k = j; k <= i; k++) --it; } printf("%d ", *it); num.erase(it); break; } } } 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 | #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <set> typedef long long ll; const int N = 2.5e5 + 5; const ll inf = 1ll << 60; using namespace std; vector<ll> dp[N]; set<int> num; ll size[N], k; int n; ll count(int n, ll k) { if (k < 0 || k > size[n]) return 0; k = min(k, (ll)size[n] - k); if (k >= dp[n].size()) return inf + inf; else return dp[n][k]; } int main() { scanf("%d%lld", &n, &k); for (int i = 1; i <= n; i++) { size[i] = (ll)i * (i - 1) / 2; } dp[0]= dp[1] = vector<ll> {1}; for (int i = 2; i <= n; i++) { ll tmp = 0; for (int j = 0; j <= size[i]; j++) { tmp += count(i - 1, j) - count(i - 1, j - i); if (tmp > inf) break; dp[i].push_back(tmp); } } if (size[n] % 2 != 0 || count(n, size[n] / 2) < k) { puts("NIE"); return 0; } puts("TAK"); ll m = size[n] / 2; for (int i = 1; i <= n; i++) num.insert(i); for (int i = n - 1; i >= 0; i--) { ll rem = size[i]; for (int j = max(0ll, m - rem); j <= i; j++) { ll tmp = count(i, m - j); if (tmp < k) k -= tmp; else { m -= j; auto it = num.begin(); if (2 * j < i + 1) { for (int k = 0; k < j; k++) ++it; } else { it = num.end(); for (int k = j; k <= i; k++) --it; } printf("%d ", *it); num.erase(it); break; } } } puts(""); } |