#include <cstdio> #include <vector> const long long X = 23, XX = 300; int num[250001]; long long a[X][XX]; std::vector<int> output; void compute(long long lwl, long long poz, long long k); long long min(long long a, long long b) { return a < b ? a : b; } void print(int a, long long n) { // printf("Szukamy %d-tej z kolei\n", a); for (int i = 1; i <= n; i++) { if (num[i] == false) { a--; }// else printf("to: %d juz zajete zostalo %d\n", i, a); if (a == 0 && num[i] == false) { num[i] = true; a = i; break; } } printf("%d ", a); } int main() { long long n, k, maks; scanf("%Ld%Ld", &n, &k); maks = (n - 1) * n / 2; if (maks % 2 != 0 || k > maks) { printf("NIE\n"); return 0; } long long poz = maks / 2; long long MM = X * (X - 1) / 2; a[1][0] = 1; for (int i = 2; i <= min(n, X - 1); i++) { for (int j = 0; j <= i * (i - 1) / 2; j++) { if (j < i && j >= 1) { // printf("JEDEN\n"); a[i][j] = i - 1 <= 0 ? 1 : a[i][j - 1]; a[i][j] += n - 1 <= 0 ? 1 : a[i - 1][j]; } else { // printf("TRZY %Ld %Ld\n", i, j); a[i][j] = a[i][j - 1]; a[i][j] += a[i - 1][j]; a[i][j] -= a[i - 1][j - i]; // printf("DWA %Ld = %Ld + %Ld - %Ld\n", a[i][j], a[i][j - 1], a[i - 1][j], a[i - 1][j - i]); } // printf("a[%d][%d] = %Ld\n", i, j, a[i][j]); } } long long full = 0; while (poz > MM) { poz -= MM; full++; // printf("FULL %Ld %Ld %Ld\n", full, n, poz); } for (int i = 0; i < full; i++) { // printf("COMP %d\n", i); compute(min(n, X - 1), poz, 1); } compute(min(n, X - 1), poz, k); // for (int i = 1; i <= n - X + 1; i++) { // printf("%d ", i); // } printf("TAK\n"); for (size_t i = 0; i < output.size(); i++) { print(output[i], n); } print(1, n); return 0; } void compute(long long lwl, long long poz, long long k) { while (lwl > 1) { for (int i = 1; i <= lwl; i++) { // printf("w przedz %d jest %Ld inwersji %Ld %Ld\n", i, poz, poz - i + 1, lwl); long long b = a[lwl - 1][poz - i + 1]; // printf("w przedz %d jest %Ld %Ld inwersji %Ld %Ld\n", i, b, poz, poz - i + 1, lwl); if (k > b) { k -= b; } else { // printf("%d\n", i); output.push_back(i); lwl--; poz -= i - 1; break; } // printf("Szukane: K %Ld L %Ld N %Ld P %Ld\n", k, lwl, n, poz); } } }
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 | #include <cstdio> #include <vector> const long long X = 23, XX = 300; int num[250001]; long long a[X][XX]; std::vector<int> output; void compute(long long lwl, long long poz, long long k); long long min(long long a, long long b) { return a < b ? a : b; } void print(int a, long long n) { // printf("Szukamy %d-tej z kolei\n", a); for (int i = 1; i <= n; i++) { if (num[i] == false) { a--; }// else printf("to: %d juz zajete zostalo %d\n", i, a); if (a == 0 && num[i] == false) { num[i] = true; a = i; break; } } printf("%d ", a); } int main() { long long n, k, maks; scanf("%Ld%Ld", &n, &k); maks = (n - 1) * n / 2; if (maks % 2 != 0 || k > maks) { printf("NIE\n"); return 0; } long long poz = maks / 2; long long MM = X * (X - 1) / 2; a[1][0] = 1; for (int i = 2; i <= min(n, X - 1); i++) { for (int j = 0; j <= i * (i - 1) / 2; j++) { if (j < i && j >= 1) { // printf("JEDEN\n"); a[i][j] = i - 1 <= 0 ? 1 : a[i][j - 1]; a[i][j] += n - 1 <= 0 ? 1 : a[i - 1][j]; } else { // printf("TRZY %Ld %Ld\n", i, j); a[i][j] = a[i][j - 1]; a[i][j] += a[i - 1][j]; a[i][j] -= a[i - 1][j - i]; // printf("DWA %Ld = %Ld + %Ld - %Ld\n", a[i][j], a[i][j - 1], a[i - 1][j], a[i - 1][j - i]); } // printf("a[%d][%d] = %Ld\n", i, j, a[i][j]); } } long long full = 0; while (poz > MM) { poz -= MM; full++; // printf("FULL %Ld %Ld %Ld\n", full, n, poz); } for (int i = 0; i < full; i++) { // printf("COMP %d\n", i); compute(min(n, X - 1), poz, 1); } compute(min(n, X - 1), poz, k); // for (int i = 1; i <= n - X + 1; i++) { // printf("%d ", i); // } printf("TAK\n"); for (size_t i = 0; i < output.size(); i++) { print(output[i], n); } print(1, n); return 0; } void compute(long long lwl, long long poz, long long k) { while (lwl > 1) { for (int i = 1; i <= lwl; i++) { // printf("w przedz %d jest %Ld inwersji %Ld %Ld\n", i, poz, poz - i + 1, lwl); long long b = a[lwl - 1][poz - i + 1]; // printf("w przedz %d jest %Ld %Ld inwersji %Ld %Ld\n", i, b, poz, poz - i + 1, lwl); if (k > b) { k -= b; } else { // printf("%d\n", i); output.push_back(i); lwl--; poz -= i - 1; break; } // printf("Szukane: K %Ld L %Ld N %Ld P %Ld\n", k, lwl, n, poz); } } } |