#include <cstdio> #include <algorithm> #include <cmath> using namespace std; int *t, n; long long k; long long inv(int *p) { long long r = 0; int ln = log2(n) + 1; int *c = new int[n]; for (int i=0; i<n; i++) c[i]=0; while (ln--) { for (int i=0; i<n; i++) { if (p[i]%2!=0) c[p[i]-1] = c[p[i]-1] + 1; else r = r + c[p[i]] ; } for (int i=0; i<n; i++) { c[i] = 0; p[i] = p[i] / 2; } } delete []c; return r; } long long rev_inv(int *p) { long long r = 0; int ln = log2(n) + 1; int *c = new int[n]; for (int i=0; i<n; i++) c[i]=0; while (ln--) { for (int i=n-1; i>=0; i--) { if (p[i]%2!=0) c[p[i]-1] = c[p[i]-1] + 1; else r = r + c[p[i]] ; } for (int i=n-1; i>=0; i--) { c[i] = 0; p[i] = p[i] / 2; } } delete []c; return r; } int main() { scanf("%d %lld", &n, &k); int *t = new int[n]; long long s = 0; for (int i = 0; i < n; i++) t[i] = i+1; while (true) { int *tc = new int[n]; int *tci = new int[n]; for (int i=0; i<n; i++) { tc[i] = t[i]; tci[i] = t[i]; } if (inv(tc) == rev_inv(tci)) { s++; if (s==k) { printf("%s","TAK\n"); for (int i = 0; i < n; i++) printf("%d ", t[i]); break; } } delete []tc; delete []tci; /* Szukamy najdalszego elementu do zamiany */ int i = n - 1; while (i > 0 && t[i - 1] >= t[i]) i--; if (i == 0) { /* Ciag posortowany nierosnaco */ printf("%s","NIE"); break; } /* Wykonujemy zamiane */ int j = i; while (j < n && t[j] > t[i - 1]) j++; j--; swap(t[i - 1], t[j]); reverse(t + i, t + n); } delete []t; 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 | #include <cstdio> #include <algorithm> #include <cmath> using namespace std; int *t, n; long long k; long long inv(int *p) { long long r = 0; int ln = log2(n) + 1; int *c = new int[n]; for (int i=0; i<n; i++) c[i]=0; while (ln--) { for (int i=0; i<n; i++) { if (p[i]%2!=0) c[p[i]-1] = c[p[i]-1] + 1; else r = r + c[p[i]] ; } for (int i=0; i<n; i++) { c[i] = 0; p[i] = p[i] / 2; } } delete []c; return r; } long long rev_inv(int *p) { long long r = 0; int ln = log2(n) + 1; int *c = new int[n]; for (int i=0; i<n; i++) c[i]=0; while (ln--) { for (int i=n-1; i>=0; i--) { if (p[i]%2!=0) c[p[i]-1] = c[p[i]-1] + 1; else r = r + c[p[i]] ; } for (int i=n-1; i>=0; i--) { c[i] = 0; p[i] = p[i] / 2; } } delete []c; return r; } int main() { scanf("%d %lld", &n, &k); int *t = new int[n]; long long s = 0; for (int i = 0; i < n; i++) t[i] = i+1; while (true) { int *tc = new int[n]; int *tci = new int[n]; for (int i=0; i<n; i++) { tc[i] = t[i]; tci[i] = t[i]; } if (inv(tc) == rev_inv(tci)) { s++; if (s==k) { printf("%s","TAK\n"); for (int i = 0; i < n; i++) printf("%d ", t[i]); break; } } delete []tc; delete []tci; /* Szukamy najdalszego elementu do zamiany */ int i = n - 1; while (i > 0 && t[i - 1] >= t[i]) i--; if (i == 0) { /* Ciag posortowany nierosnaco */ printf("%s","NIE"); break; } /* Wykonujemy zamiane */ int j = i; while (j < n && t[j] > t[i - 1]) j++; j--; swap(t[i - 1], t[j]); reverse(t + i, t + n); } delete []t; return 0; } |