#include <stdint.h> #include <cstdio> #include <vector> #include <set> using namespace std; #define INF 1000000000000000001 vector<vector<int64_t> > P; vector<int64_t> row_length; int64_t get(int64_t n, int64_t c) { int64_t row_len = row_length[n]; int64_t mirrored_c = row_len - c - 1; if (c<0 || c>row_len-1) return 0; if (c<P[n].size()) return P[n][c]; if (mirrored_c<P[n].size()) return P[n][mirrored_c]; return INF; } void populate(int64_t n) { row_length.clear(); row_length.resize(n+1); row_length[0] = 1; P.clear(); P.resize(n+1); P[0].push_back(1); for(int64_t i=1; i<=n; ++i) { row_length[i] = row_length[i-1] + i - 1; P[i].push_back(1); for (int64_t j=1; j<row_length[i]; ++j) { int64_t x = get(i, j-1) + get(i-1, j) - get(i-1, j-i); if (x >= INF) break; P[i].push_back(x); } } } int64_t N; int64_t K, C; int main(){ scanf("%lld %lld", &N, &K); if (N%4>1){ printf("NIE"); return 0; } populate(N); C = N*(N-1)/4; if (get(N, C) <= K-1){ printf("NIE"); return 0; } K -= 1; printf("TAK\n"); set<int32_t> D; for(int32_t i=1; i<=N; ++i) D.insert(i); for(int32_t i=0; i<N; ++i) { int64_t init_d = C-row_length[N-i-1]+1; if (init_d < 0) init_d = 0; for(int64_t d=init_d; d<N-i; ++d) { int64_t sub_factor = get(N-i-1, C-d); if (sub_factor <= K) { K = K - sub_factor; continue; } else { C = C - d; set<int32_t>::iterator it; if (d < D.size()-d-1) { it = D.begin(); for(int32_t j=0; j!=d; ++j) ++it; } else { it = D.end(); for(int32_t j=D.size(); j!=d; --j) --it; } printf("%d ", *it); D.erase(it); break; } } } }
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 | #include <stdint.h> #include <cstdio> #include <vector> #include <set> using namespace std; #define INF 1000000000000000001 vector<vector<int64_t> > P; vector<int64_t> row_length; int64_t get(int64_t n, int64_t c) { int64_t row_len = row_length[n]; int64_t mirrored_c = row_len - c - 1; if (c<0 || c>row_len-1) return 0; if (c<P[n].size()) return P[n][c]; if (mirrored_c<P[n].size()) return P[n][mirrored_c]; return INF; } void populate(int64_t n) { row_length.clear(); row_length.resize(n+1); row_length[0] = 1; P.clear(); P.resize(n+1); P[0].push_back(1); for(int64_t i=1; i<=n; ++i) { row_length[i] = row_length[i-1] + i - 1; P[i].push_back(1); for (int64_t j=1; j<row_length[i]; ++j) { int64_t x = get(i, j-1) + get(i-1, j) - get(i-1, j-i); if (x >= INF) break; P[i].push_back(x); } } } int64_t N; int64_t K, C; int main(){ scanf("%lld %lld", &N, &K); if (N%4>1){ printf("NIE"); return 0; } populate(N); C = N*(N-1)/4; if (get(N, C) <= K-1){ printf("NIE"); return 0; } K -= 1; printf("TAK\n"); set<int32_t> D; for(int32_t i=1; i<=N; ++i) D.insert(i); for(int32_t i=0; i<N; ++i) { int64_t init_d = C-row_length[N-i-1]+1; if (init_d < 0) init_d = 0; for(int64_t d=init_d; d<N-i; ++d) { int64_t sub_factor = get(N-i-1, C-d); if (sub_factor <= K) { K = K - sub_factor; continue; } else { C = C - d; set<int32_t>::iterator it; if (d < D.size()-d-1) { it = D.begin(); for(int32_t j=0; j!=d; ++j) ++it; } else { it = D.end(); for(int32_t j=D.size(); j!=d; --j) --it; } printf("%d ", *it); D.erase(it); break; } } } } |