// PA2017, Permutacje // Andrzej Pezarski #include <cstdio> #include <vector> using namespace std; const long long INF=1000000000000000001LL; struct Drzewko { int L; vector<int> T; Drzewko(int n) { L=1; while (L<n) L*=2; T.resize(2*L); for (int i=L; i<2*L; i++) T[i]=1; for (int i=L-1; i>0; i--) T[i]=T[2*i]+T[2*i+1]; } int f(int k) { int v=1; while(v<L) { T[v]--; if (T[2*v]<=k) { k-=T[2*v]; v=2*v+1; } else v=2*v; } T[v]--; return v-L; } }; struct Tabelka { vector<vector<long long> > T; Tabelka(long long N) { T.resize(N+1); T[1].push_back(1); for (long long n=2; n<=N; n++) { long long maxI=n*(n-1)/2; long long sum=0; for (int a=-n, b=0; b<=maxI; a++, b++) { sum+=((a>=0&&a<T[n-1].size())?-T[n-1][a]:0LL)+(b<T[n-1].size()?T[n-1][b]:0LL); sum=min(sum, INF); T[n].push_back(sum); if (sum==INF) break; } } } long long f(long long n, long long i){ long long maxI=n*(n-1)/2; i=min(i, maxI-i); if (i<0) return 0LL; if (i>=T[n].size()) return INF; return T[n][i]; } }; int main() { long long N; long long K; scanf("%lld%lld", &N, &K); if ((N*(N-1)/2)%2) { printf("NIE\n"); return 0; } long long I=N*(N-1)/4; Tabelka T(N); if (T.f(N, I)<K){ printf("NIE\n"); return 0; } vector<int> RES; Drzewko D(N); while(N>1) { long long maxI2=(N-1)*(N-2)/2; long long i=max(0LL, I-maxI2); I-=i; while (T.f(N-1, I)<K) { K-=T.f(N-1, I); i++; I--; } RES.push_back(i); N--; } RES.push_back(0); printf("TAK\n"); for (int i=0; i<RES.size(); i++) { printf("%d ", D.f(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 | // PA2017, Permutacje // Andrzej Pezarski #include <cstdio> #include <vector> using namespace std; const long long INF=1000000000000000001LL; struct Drzewko { int L; vector<int> T; Drzewko(int n) { L=1; while (L<n) L*=2; T.resize(2*L); for (int i=L; i<2*L; i++) T[i]=1; for (int i=L-1; i>0; i--) T[i]=T[2*i]+T[2*i+1]; } int f(int k) { int v=1; while(v<L) { T[v]--; if (T[2*v]<=k) { k-=T[2*v]; v=2*v+1; } else v=2*v; } T[v]--; return v-L; } }; struct Tabelka { vector<vector<long long> > T; Tabelka(long long N) { T.resize(N+1); T[1].push_back(1); for (long long n=2; n<=N; n++) { long long maxI=n*(n-1)/2; long long sum=0; for (int a=-n, b=0; b<=maxI; a++, b++) { sum+=((a>=0&&a<T[n-1].size())?-T[n-1][a]:0LL)+(b<T[n-1].size()?T[n-1][b]:0LL); sum=min(sum, INF); T[n].push_back(sum); if (sum==INF) break; } } } long long f(long long n, long long i){ long long maxI=n*(n-1)/2; i=min(i, maxI-i); if (i<0) return 0LL; if (i>=T[n].size()) return INF; return T[n][i]; } }; int main() { long long N; long long K; scanf("%lld%lld", &N, &K); if ((N*(N-1)/2)%2) { printf("NIE\n"); return 0; } long long I=N*(N-1)/4; Tabelka T(N); if (T.f(N, I)<K){ printf("NIE\n"); return 0; } vector<int> RES; Drzewko D(N); while(N>1) { long long maxI2=(N-1)*(N-2)/2; long long i=max(0LL, I-maxI2); I-=i; while (T.f(N-1, I)<K) { K-=T.f(N-1, I); i++; I--; } RES.push_back(i); N--; } RES.push_back(0); printf("TAK\n"); for (int i=0; i<RES.size(); i++) { printf("%d ", D.f(RES[i])+1); } printf("\n"); return 0; } |