#include <cstdio> #include <cstdlib> #include <bitset> #include <cstring> #include <vector> const int N = 250000; void print_perm(FILE *fp, std::vector<int> &perm) { for (int i = 0; i< perm.size(); ++i) { fprintf(fp, "%d ", perm[i] + 1); } fprintf(fp, "\n"); } long long int count_inversions(std::vector<int> &perm) { int n = perm.size(); long long int inv = 0; for (int i = 0; i< n; ++i) { for (int j = i + 1; j< n; ++j) { if (perm[i] > perm[j]) { ++inv; } } } return inv; } bool generate(std::vector<int> &perm, std::bitset<N> &disabled, long long int k, int i, long long int inv, long long int &cnt) { int n = perm.size(); if (i == n) { //print_perm(stderr, perm); long long int perm_inv = count_inversions(perm); if (perm_inv == inv) { //fprintf(stderr,"perm_invcnt %d\n", perm_inv); if (k == cnt) { //fprintf(stderr,"HA %d %d\n", k, cnt); printf("TAK\n"); print_perm(stdout, perm); return true; } cnt++; } return false; } bool found = false; for (int j = 0; j < perm.size(); ++j) { if (disabled.test(j)) { continue; } perm[i] = j; disabled.set(j); if(generate(perm, disabled, k, i + 1, inv, cnt)) { return true; } disabled.reset(j); } return found; } int main() { std::vector<int> perm; std::bitset<N> disabled; int n; long long int k; scanf("%d", &n); scanf("%lld", &k); k--; perm.resize(n); for (int i = 0; i <n; ++i) { perm[i] = i; } long long int num_of_perms = n * (n - 1) /2; long long int cnt = 0; if (num_of_perms % 2 == 0) { if (!generate(perm, disabled, k, 0, num_of_perms / 2, cnt)) { printf("NIE\n"); } } else { printf("NIE\n"); } }
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 | #include <cstdio> #include <cstdlib> #include <bitset> #include <cstring> #include <vector> const int N = 250000; void print_perm(FILE *fp, std::vector<int> &perm) { for (int i = 0; i< perm.size(); ++i) { fprintf(fp, "%d ", perm[i] + 1); } fprintf(fp, "\n"); } long long int count_inversions(std::vector<int> &perm) { int n = perm.size(); long long int inv = 0; for (int i = 0; i< n; ++i) { for (int j = i + 1; j< n; ++j) { if (perm[i] > perm[j]) { ++inv; } } } return inv; } bool generate(std::vector<int> &perm, std::bitset<N> &disabled, long long int k, int i, long long int inv, long long int &cnt) { int n = perm.size(); if (i == n) { //print_perm(stderr, perm); long long int perm_inv = count_inversions(perm); if (perm_inv == inv) { //fprintf(stderr,"perm_invcnt %d\n", perm_inv); if (k == cnt) { //fprintf(stderr,"HA %d %d\n", k, cnt); printf("TAK\n"); print_perm(stdout, perm); return true; } cnt++; } return false; } bool found = false; for (int j = 0; j < perm.size(); ++j) { if (disabled.test(j)) { continue; } perm[i] = j; disabled.set(j); if(generate(perm, disabled, k, i + 1, inv, cnt)) { return true; } disabled.reset(j); } return found; } int main() { std::vector<int> perm; std::bitset<N> disabled; int n; long long int k; scanf("%d", &n); scanf("%lld", &k); k--; perm.resize(n); for (int i = 0; i <n; ++i) { perm[i] = i; } long long int num_of_perms = n * (n - 1) /2; long long int cnt = 0; if (num_of_perms % 2 == 0) { if (!generate(perm, disabled, k, 0, num_of_perms / 2, cnt)) { printf("NIE\n"); } } else { printf("NIE\n"); } } |