#include<bits/stdc++.h> using namespace std; int N, sz[250009]; long long INF = 1e18, K, *dp[250009]; namespace brute { int N, p[20]; void solve () { scanf ("%d", &N); for (int i=1; i<=N; i++) p[i] = i; do { int cnt = 0; for (int i=1; i<=N; i++) for (int j=i+1; j<=N; j++) cnt += (p[i] > p[j]); if (cnt + cnt == N * (N - 1) / 2) for (int i=1; i<=N; i++) printf ("%d%c", p[i], " \n"[i == N]); }while (next_permutation (p + 1, p + N + 1)); } } long long getDp (int i, int j) { if (j > 1LL * i * (i - 1) / 2) return 0; if (j <= sz[i]) return dp[i][j]; if (1LL * i * (i - 1) / 2 - j <= sz[i]) return dp[i][i * (i - 1) / 2 - j]; return INF + 1; } void buildDp (int N) { dp[0] = new long long[1], dp[0][0] = 1, sz[0] = 0; for (int i=1; i<=N; i++) { vector < long long > curr; for (int j=0; j<=1LL * i * (i - 1) / 2; j++) { long long val = 0; val = 0; for (int k=0; k<i && k<=j; k++) { val += getDp (i - 1, j - k); if (val > INF) { val = INF + 1; break; } } if (val <= INF) sz[i] = j; else break; curr.push_back (val); } dp[i] = new long long[sz[i] + 1]; for (int j=0; j<=sz[i]; j++) dp[i][j] = curr[j]; } } int Size;bool isInside[250009];priority_queue < int > grtst, smlst; void add (int x){if (isInside[x]) return ; Size ++; grtst.push (x), smlst.push (-x), isInside[x] = 1;} void del (int x) {Size -= isInside[x]; isInside[x] = 0;} int getSmall (){while (!smlst.empty ()){int curr = -smlst.top (); smlst.pop ();if (isInside[curr]) {del (curr);return curr;}}return -1;} int getLarge (){while (!grtst.empty ()){int curr = grtst.top (); grtst.pop ();if (isInside[curr]) {del (curr);return curr;}}return -1;} void solve (long long val, long long cnt) { int L = Size; if (L == 0) return ; vector < int > soFar; int pos = 1, curr; while (1) { curr = getSmall (); if (val <= getDp (L - 1, cnt - (pos - 1))) break; else val -= getDp (L - 1, cnt - (pos - 1)); soFar.push_back (curr), pos ++; } printf ("%d ", curr); for (auto it : soFar) add (it); solve (val, cnt - (pos - 1)); } int main () { //freopen ("input", "r", stdin); //freopen ("output", "w", stdout); scanf ("%d %lld", &N, &K); if (N % 4 == 2 || N % 4 == 3) { printf ("NIE\n"); return 0; } buildDp (N); if (N <= 50 && getDp (N, N * (N - 1) / 4) < K) { printf ("NIE\n"); return 0; } printf ("TAK\n"); for (int i=1; i<=N; i++) add (i); solve (K, 1LL * N * (N - 1) / 4); 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 114 115 116 | #include<bits/stdc++.h> using namespace std; int N, sz[250009]; long long INF = 1e18, K, *dp[250009]; namespace brute { int N, p[20]; void solve () { scanf ("%d", &N); for (int i=1; i<=N; i++) p[i] = i; do { int cnt = 0; for (int i=1; i<=N; i++) for (int j=i+1; j<=N; j++) cnt += (p[i] > p[j]); if (cnt + cnt == N * (N - 1) / 2) for (int i=1; i<=N; i++) printf ("%d%c", p[i], " \n"[i == N]); }while (next_permutation (p + 1, p + N + 1)); } } long long getDp (int i, int j) { if (j > 1LL * i * (i - 1) / 2) return 0; if (j <= sz[i]) return dp[i][j]; if (1LL * i * (i - 1) / 2 - j <= sz[i]) return dp[i][i * (i - 1) / 2 - j]; return INF + 1; } void buildDp (int N) { dp[0] = new long long[1], dp[0][0] = 1, sz[0] = 0; for (int i=1; i<=N; i++) { vector < long long > curr; for (int j=0; j<=1LL * i * (i - 1) / 2; j++) { long long val = 0; val = 0; for (int k=0; k<i && k<=j; k++) { val += getDp (i - 1, j - k); if (val > INF) { val = INF + 1; break; } } if (val <= INF) sz[i] = j; else break; curr.push_back (val); } dp[i] = new long long[sz[i] + 1]; for (int j=0; j<=sz[i]; j++) dp[i][j] = curr[j]; } } int Size;bool isInside[250009];priority_queue < int > grtst, smlst; void add (int x){if (isInside[x]) return ; Size ++; grtst.push (x), smlst.push (-x), isInside[x] = 1;} void del (int x) {Size -= isInside[x]; isInside[x] = 0;} int getSmall (){while (!smlst.empty ()){int curr = -smlst.top (); smlst.pop ();if (isInside[curr]) {del (curr);return curr;}}return -1;} int getLarge (){while (!grtst.empty ()){int curr = grtst.top (); grtst.pop ();if (isInside[curr]) {del (curr);return curr;}}return -1;} void solve (long long val, long long cnt) { int L = Size; if (L == 0) return ; vector < int > soFar; int pos = 1, curr; while (1) { curr = getSmall (); if (val <= getDp (L - 1, cnt - (pos - 1))) break; else val -= getDp (L - 1, cnt - (pos - 1)); soFar.push_back (curr), pos ++; } printf ("%d ", curr); for (auto it : soFar) add (it); solve (val, cnt - (pos - 1)); } int main () { //freopen ("input", "r", stdin); //freopen ("output", "w", stdout); scanf ("%d %lld", &N, &K); if (N % 4 == 2 || N % 4 == 3) { printf ("NIE\n"); return 0; } buildDp (N); if (N <= 50 && getDp (N, N * (N - 1) / 4) < K) { printf ("NIE\n"); return 0; } printf ("TAK\n"); for (int i=1; i<=N; i++) add (i); solve (K, 1LL * N * (N - 1) / 4); printf ("\n"); return 0; } |