#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; typedef long long LL; const LL K=1000000000000000000LL; map<pair<int, LL>, LL> lPer;//<n, li> LL liczPer(LL n, LL li) { LL ma=n*(n-1)/2; if (ma/2<li) li=ma-li; if (li==1) return n-1; if (li<0) return 0; if (li==0) return 1; if (n<2) return 1; map<pair<int, LL>, LL>::iterator it=lPer.find(make_pair(n, li)); if (it!=lPer.end()) return it->second; LL wyn=0; for (int i=0; i<n && wyn<K && i<=li; ++i) wyn+=liczPer(n-1, li-i); wyn=min(wyn, K); lPer[make_pair(n, li)]=wyn; return wyn; } vector<int> elty, wyn; bool przyspiesz(int x, int &pe, LL li, LL k) { LL n=elty.size()-pe; if (x<n && k<=liczPer(n-x, li)) { for (int i=0; i<x; ++i) wyn.push_back(elty[pe+i]); pe+=x; return true; } return false; } bool jest(LL li, LL k) { int pe=0; int x=200000; while (1<x) { while (przyspiesz(x, pe, li, k)) ; x/=2; } for (; pe<elty.size(); ) { LL n=elty.size()-pe; // cerr<<n<<' '<<li<<'\t'<<k<<'\t'<<lPer.size()<<endl; if (n==1) { wyn.push_back(elty[pe]); break; } int ii=-1; for (int i=0; i<n; ++i) { LL lp=liczPer(n-1, li); if (k<=lp) { ii=i; break; } k-=lp; --li; } if (ii==-1) return false; wyn.push_back(elty[pe+ii]); if (ii==0) ++pe; else { elty.erase(elty.begin()+(pe+ii)); //cerr<<ii<<endl; } } return li==0 && k==1; } int main() { ios_base::sync_with_stdio(false); LL n, k, lp; cin>>n>>k; for (int i=0; i<n; ++i) elty.push_back(i+1); lp=n*(n-1)/2; if (lp%2 || !jest(lp/2, k)) cout<<"NIE"<<endl; else { cout<<"TAK"<<endl; for (int i=0; i<n; ++i) cout<<wyn[i]<<' '; cout<<endl; } 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 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 119 | #include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; typedef long long LL; const LL K=1000000000000000000LL; map<pair<int, LL>, LL> lPer;//<n, li> LL liczPer(LL n, LL li) { LL ma=n*(n-1)/2; if (ma/2<li) li=ma-li; if (li==1) return n-1; if (li<0) return 0; if (li==0) return 1; if (n<2) return 1; map<pair<int, LL>, LL>::iterator it=lPer.find(make_pair(n, li)); if (it!=lPer.end()) return it->second; LL wyn=0; for (int i=0; i<n && wyn<K && i<=li; ++i) wyn+=liczPer(n-1, li-i); wyn=min(wyn, K); lPer[make_pair(n, li)]=wyn; return wyn; } vector<int> elty, wyn; bool przyspiesz(int x, int &pe, LL li, LL k) { LL n=elty.size()-pe; if (x<n && k<=liczPer(n-x, li)) { for (int i=0; i<x; ++i) wyn.push_back(elty[pe+i]); pe+=x; return true; } return false; } bool jest(LL li, LL k) { int pe=0; int x=200000; while (1<x) { while (przyspiesz(x, pe, li, k)) ; x/=2; } for (; pe<elty.size(); ) { LL n=elty.size()-pe; // cerr<<n<<' '<<li<<'\t'<<k<<'\t'<<lPer.size()<<endl; if (n==1) { wyn.push_back(elty[pe]); break; } int ii=-1; for (int i=0; i<n; ++i) { LL lp=liczPer(n-1, li); if (k<=lp) { ii=i; break; } k-=lp; --li; } if (ii==-1) return false; wyn.push_back(elty[pe+ii]); if (ii==0) ++pe; else { elty.erase(elty.begin()+(pe+ii)); //cerr<<ii<<endl; } } return li==0 && k==1; } int main() { ios_base::sync_with_stdio(false); LL n, k, lp; cin>>n>>k; for (int i=0; i<n; ++i) elty.push_back(i+1); lp=n*(n-1)/2; if (lp%2 || !jest(lp/2, k)) cout<<"NIE"<<endl; else { cout<<"TAK"<<endl; for (int i=0; i<n; ++i) cout<<wyn[i]<<' '; cout<<endl; } return 0; } |