#include <bits/stdc++.h> using namespace std; #define REP(i, n) for (int i=0, ___=(n); i<___; ++i) #define FOR(i, a, b) for (int i=(a), ___=(b); i<=___; ++i) typedef long long ll; typedef pair<int, int> PII; typedef pair<int, ll> PIL; int read() { int n; cin >> n; return n; } const ll mm = 1000000000000000001LL; vector<vector<ll> > v; void foo(int n, ll k, int inv, set<int> &s) { while (n > 2) { for (set<int>::iterator it = s.begin(); it != s.end(); ++it) { ll cur = inv < v[n-1].size() ? v[n-1][inv] : v[n-1].back() == 1 ? 0 : mm; if (k > cur) { k -= cur; --inv; continue; } cout << *it << " "; s.erase(it); break; } --n; } if (n == 1) { cout << *s.begin() << "\n"; return; } int a = *s.begin(); int b = *s.rbegin(); if (inv == 0) { cout << a << " " << b << "\n"; return; } cout << b << " " << a << "\n"; return; } int main() { int n = read(); ll k; cin >> k; if (n % 4 == 2 || n % 4 == 3) { cout << "NIE\n"; return 0; } v.push_back(vector<ll>()); v.push_back(vector<ll>(1, 1)); FOR(nn, 2, n) { v.push_back(vector<ll>(1, 1)); FOR(inv, 1, 1LL * nn * (nn-1) / 2) { ll up = inv < v[nn-1].size() ? v[nn-1][inv] : v[nn-1].back() == 1 ? 0 : mm; ll down = inv >= nn ? v[nn-1][inv - nn] : 0; ll cur = v[nn][inv-1] + up - down; if (cur > mm) cur = mm; v[nn].push_back(cur); if (cur == mm) break; } } ll inv = 1LL * n * (n-1) / 4; ll cnt = inv < v[n].size() ? v[n][inv] : mm; if (k > cnt) { cout << "NIE\n"; return 0; } cout << "TAK\n"; set<int> s; REP(i, n) s.insert(i+1); foo(n, k, inv, s); 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 78 79 80 81 82 83 84 | #include <bits/stdc++.h> using namespace std; #define REP(i, n) for (int i=0, ___=(n); i<___; ++i) #define FOR(i, a, b) for (int i=(a), ___=(b); i<=___; ++i) typedef long long ll; typedef pair<int, int> PII; typedef pair<int, ll> PIL; int read() { int n; cin >> n; return n; } const ll mm = 1000000000000000001LL; vector<vector<ll> > v; void foo(int n, ll k, int inv, set<int> &s) { while (n > 2) { for (set<int>::iterator it = s.begin(); it != s.end(); ++it) { ll cur = inv < v[n-1].size() ? v[n-1][inv] : v[n-1].back() == 1 ? 0 : mm; if (k > cur) { k -= cur; --inv; continue; } cout << *it << " "; s.erase(it); break; } --n; } if (n == 1) { cout << *s.begin() << "\n"; return; } int a = *s.begin(); int b = *s.rbegin(); if (inv == 0) { cout << a << " " << b << "\n"; return; } cout << b << " " << a << "\n"; return; } int main() { int n = read(); ll k; cin >> k; if (n % 4 == 2 || n % 4 == 3) { cout << "NIE\n"; return 0; } v.push_back(vector<ll>()); v.push_back(vector<ll>(1, 1)); FOR(nn, 2, n) { v.push_back(vector<ll>(1, 1)); FOR(inv, 1, 1LL * nn * (nn-1) / 2) { ll up = inv < v[nn-1].size() ? v[nn-1][inv] : v[nn-1].back() == 1 ? 0 : mm; ll down = inv >= nn ? v[nn-1][inv - nn] : 0; ll cur = v[nn][inv-1] + up - down; if (cur > mm) cur = mm; v[nn].push_back(cur); if (cur == mm) break; } } ll inv = 1LL * n * (n-1) / 4; ll cnt = inv < v[n].size() ? v[n][inv] : mm; if (k > cnt) { cout << "NIE\n"; return 0; } cout << "TAK\n"; set<int> s; REP(i, n) s.insert(i+1); foo(n, k, inv, s); return 0; } |