#include <iostream> #include <algorithm> using namespace std; typedef int number; #define MAXN 250000 #define EXIT_GRACEFULLY delete[] temp;\ return 0; bool odd(number i); int log(int n); int licz[MAXN]; //Rytter algorithm int inversionNumber(number perm[], int n) { int result = 0; for (int i = 0; i < log(n); ++i) { for (int j = 0; j < n; ++j) { if(odd(perm[j])) { licz[perm[j]] += 1; } else { result += licz[perm[j] + 1]; } } for (int j = 0; j < n; ++j) { licz[j] = 0; perm[j] /= 2; } } return result; } int pairNumber(int n) { return n * (n-1) / 2; } int log(int n) { char exponent = 0; while(n != 0) { n >>= 1; exponent++; } return exponent; } bool odd(number i) { return i & 1; } void print(number pInt[], int n) { for (int i = 0; i < n; ++i) { cout << pInt[i] << " "; } cout << endl; } int main() { int n; long long k = 1; long long kDesired; number perm[MAXN]; cin >> n >> kDesired; const int pn = pairNumber(n) / 2; number *temp = new number[n]; iota(perm, perm+n, 1); bool found = true; do { copy(perm, perm+n, temp); if(pn == inversionNumber(temp, n)) { if(k == kDesired) { cout << "TAK" << endl; print(perm, n); break; } k++; } } while (found = next_permutation(perm, perm+n)); if(!found) { cout << "NIE" << endl; } EXIT_GRACEFULLY }
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 | #include <iostream> #include <algorithm> using namespace std; typedef int number; #define MAXN 250000 #define EXIT_GRACEFULLY delete[] temp;\ return 0; bool odd(number i); int log(int n); int licz[MAXN]; //Rytter algorithm int inversionNumber(number perm[], int n) { int result = 0; for (int i = 0; i < log(n); ++i) { for (int j = 0; j < n; ++j) { if(odd(perm[j])) { licz[perm[j]] += 1; } else { result += licz[perm[j] + 1]; } } for (int j = 0; j < n; ++j) { licz[j] = 0; perm[j] /= 2; } } return result; } int pairNumber(int n) { return n * (n-1) / 2; } int log(int n) { char exponent = 0; while(n != 0) { n >>= 1; exponent++; } return exponent; } bool odd(number i) { return i & 1; } void print(number pInt[], int n) { for (int i = 0; i < n; ++i) { cout << pInt[i] << " "; } cout << endl; } int main() { int n; long long k = 1; long long kDesired; number perm[MAXN]; cin >> n >> kDesired; const int pn = pairNumber(n) / 2; number *temp = new number[n]; iota(perm, perm+n, 1); bool found = true; do { copy(perm, perm+n, temp); if(pn == inversionNumber(temp, n)) { if(k == kDesired) { cout << "TAK" << endl; print(perm, n); break; } k++; } } while (found = next_permutation(perm, perm+n)); if(!found) { cout << "NIE" << endl; } EXIT_GRACEFULLY } |