QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768972 | #7778. Turning Permutation | ucup-team5217# | RE | 0ms | 3680kb | C++23 | 2.9kb | 2024-11-21 15:31:41 | 2024-11-21 15:31:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define maxn 55
typedef __int128_t int128_t;
const int128_t LIM = 2e18;
bool vis[maxn];
int a[maxn];
int64_t f[maxn][maxn][3], g[2][maxn];
int64_t C[maxn][maxn];
void add(int64_t &a, int128_t w) { return a = min(LIM, a + min(w, LIM)), void(); }
void solve(void) {
int n;
int64_t k;
cin >> n >> k;
// if (n == 3) {
// if (k == 1)
// cout << "1 3 2" << endl;
// else if (k == 2)
// cout << "2 1 3" << endl;
// else if (k == 3)
// cout << "2 3 1" << endl;
// else if (k == 4)
// cout << "3 1 2" << endl;
// else
// cout << -1 << endl;
// return;
// }
f[0][0][0] = 1;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
for (int k = 0; k < 3; k++) {
if (!f[i - 1][j][k]) continue;
int128_t w = f[i - 1][j][k];
add(f[i][j + 1][k], w);
if (j >= 2) add(f[i][j - 1][k], w * j * (j - 1));
if (j >= 1 && k >= 1) add(f[i][j - 1][k], w * j * k);
if (k < 2) {
add(f[i][j][k + 1], w);
if (j >= 1) add(f[i][j - 1][k + 1], w * j);
}
}
if ((f[n - 1][0][1] + f[n - 1][0][2]) * 2 < k) return cout << -1 << endl, void();
for (int i = 1; i <= n; i++) g[0][i] = f[i][1][0], g[1][i] = f[i][0][1];
auto getNum = [&](void) -> int128_t {
int128_t ans = 1;
int tot = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = l;
if (vis[l]) continue;
while (r < n && !vis[r + 1]) r++;
ans = min(LIM, ans * g[l == 1 || r == n][r - l + 1]);
ans = min(LIM, ans * C[tot + r - l + 1][tot]), tot += r - l + 1;
}
return ans;
};
vis[0] = vis[n + 1] = true;
for (a[1] = 1; a[1] <= n; a[1]++) {
vis[a[1]] = true;
int128_t w = getNum();
if (k <= w) break;
vis[a[1]] = false, k -= w;
}
assert(a[1] <= n);
bool way = a[1] & 1;
for (int i = 2; i <= n; i++) {
for (a[i] = 1; a[i] <= n; a[i]++) {
if (vis[a[i]]) continue;
vis[a[i]] = true;
if (((a[i] & 1) ^ way) && (!vis[a[i] - 1] || !vis[a[i] + 1])) continue;
int128_t w = getNum();
if (k <= w) break;
vis[a[i]] = false, k -= w;
}
assert(a[i] <= n);
}
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
cout << endl;
return;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
for (int i = 0; i < maxn; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) add(C[i][j], C[i - 1][j - 1] + C[i - 1][j]);
}
int _ = 1;
while (_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3680kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
4 6
output:
3 1 2 4
result:
ok 4 number(s): "3 1 2 4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Runtime Error
input:
3 1