#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 } |
English