#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 300300; const ll inf = 1000100100200100100LL; vector<ll> dp[N]; const int M = 1<<18; int T[2*M+13]; void init() { dp[1].pb(1); for (int n = 2; n < N; n++) { ll mx = 1LL*n*(n-1)/2+1; ll prv = 1LL*(n-1)*(n-2)/2+1; if (SZ(dp[n-1]) != prv && mx>SZ(dp[n-1])) mx=SZ(dp[n-1]); for (int k=0; k<mx; k++) { ll cur = 0; for (int i = 0; i < n && i <= k; i++) { if (SZ(dp[n-1]) > k-i) cur += dp[n-1][k-i]; if (cur >= inf) { cur = inf; break; } } if (cur < inf) { dp[n].pb(cur); } else { break; } } } FOR(i,M) T[M+i]=1; for (int i=M-1; i>=1; i--) T[i]=T[i*2]+T[i*2+1]; } ll calc(int n, ll m) { fflush(stdout); ll mx = 1LL*n*(n-1)/2; if (m>mx) return 0; if (m > mx-m) m=mx-m; if (SZ(dp[n]) <= m) return inf; return dp[n][m]; } int ith(int x) { int p = 1, sl = 0; while (p < M) { if (sl + T[p*2] <= x) { p = p*2+1; sl += T[p-1]; } else p = p*2; } int ret = p-M; T[p]--; while (p>1) { p /= 2; T[p]=T[p*2]+T[p*2+1]; } return ret; } int res[N]; int main() { init(); int n; ll k; scanf("%d%lld", &n, &k); ll m = 1LL*n*(n-1)/2; if (m%2==1) { printf("NIE\n"); return 0; } m /= 2; if (SZ(dp[n]) > m && dp[n][m] < k) { printf("NIE\n"); return 0; } FOR(i,n) { ll lo = m-1LL*(n-i-1)*(n-i-2)/2; if (lo<0) lo=0; if (lo>n) lo=n; for (int c=lo; c<n; c++) { ll cur = calc(n-i-1, m-c); if (k <= cur) { res[i] = ith(c); m -= c; break; } k -= cur; } } printf("TAK\n"); FOR(i,n) printf("%d ", res[i]+1); 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 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 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 300300; const ll inf = 1000100100200100100LL; vector<ll> dp[N]; const int M = 1<<18; int T[2*M+13]; void init() { dp[1].pb(1); for (int n = 2; n < N; n++) { ll mx = 1LL*n*(n-1)/2+1; ll prv = 1LL*(n-1)*(n-2)/2+1; if (SZ(dp[n-1]) != prv && mx>SZ(dp[n-1])) mx=SZ(dp[n-1]); for (int k=0; k<mx; k++) { ll cur = 0; for (int i = 0; i < n && i <= k; i++) { if (SZ(dp[n-1]) > k-i) cur += dp[n-1][k-i]; if (cur >= inf) { cur = inf; break; } } if (cur < inf) { dp[n].pb(cur); } else { break; } } } FOR(i,M) T[M+i]=1; for (int i=M-1; i>=1; i--) T[i]=T[i*2]+T[i*2+1]; } ll calc(int n, ll m) { fflush(stdout); ll mx = 1LL*n*(n-1)/2; if (m>mx) return 0; if (m > mx-m) m=mx-m; if (SZ(dp[n]) <= m) return inf; return dp[n][m]; } int ith(int x) { int p = 1, sl = 0; while (p < M) { if (sl + T[p*2] <= x) { p = p*2+1; sl += T[p-1]; } else p = p*2; } int ret = p-M; T[p]--; while (p>1) { p /= 2; T[p]=T[p*2]+T[p*2+1]; } return ret; } int res[N]; int main() { init(); int n; ll k; scanf("%d%lld", &n, &k); ll m = 1LL*n*(n-1)/2; if (m%2==1) { printf("NIE\n"); return 0; } m /= 2; if (SZ(dp[n]) > m && dp[n][m] < k) { printf("NIE\n"); return 0; } FOR(i,n) { ll lo = m-1LL*(n-i-1)*(n-i-2)/2; if (lo<0) lo=0; if (lo>n) lo=n; for (int c=lo; c<n; c++) { ll cur = calc(n-i-1, m-c); if (k <= cur) { res[i] = ith(c); m -= c; break; } k -= cur; } } printf("TAK\n"); FOR(i,n) printf("%d ", res[i]+1); printf("\n"); return 0; } |