QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#371824 | #7778. Turning Permutation | comeintocalm# | WA | 1ms | 3904kb | C++17 | 1.9kb | 2024-03-30 16:51:48 | 2024-03-30 16:51:48 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
#define LI __int128
using namespace std;
const int MAXN = 55;
const LI inf = 1e18 + 1;
int n;
LL K;
LI f[MAXN][2][2], c[MAXN][MAXN];
#define inc(t1) ( (t1) = min ((t1), inf) )
int a[MAXN];
LI calc() {
LI ret = 1;
int cnt = 0;
for (int p = 1, q; p <= n; p = q + 1) {
q = p;
while (q <= n && a[q]) ++q;
ret *= f[q - p][p != 1][q != n + 1];
//cout << q - p << " " << (LL) f[q - p][p != 1][q != n + 1] << endl;
inc (ret);
cnt += q - p;
ret *= c[cnt][q - p];
inc (ret);
}
return ret;
}
int ans[MAXN];
void dfs (int dep, LI V) {
//cout << dep << endl;
if (dep == n && V == 1) {
for (int i = 1; i <= n; ++i)
if (a[i]) ans[n] = i;
for (int i = 1; i <= n; ++i)
printf ("%d ", ans[i]);
exit (0);
}
for (int i = 1; i <= n; ++i)
if (a[i]) {
//cout << i << " ";
a[i] = 0;
LI ret = calc();
//cout << (LL) ret << endl;
if (ret >= V) {
ans[dep] = i;
dfs (dep + 1, V);
return ;
}
else V -= ret;
a[i] = 1;
}
}
int main() {
int i,j,k;
scanf ("%d%lld", &n, &K);
for (i = 1; i <= n; ++i) a[i] = 1;
//a[1] = 0;
//calc();
//return 0;
for (i = 1, c[0][0] = 1; i <= n; ++i)
for (j = 1, c[i][0] = 1; j <= i; ++j) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
inc(c[i][j]);
}
f[0][0][0] = f[0][1][0] = f[0][0][1] = f[0][1][1] = 1;
f[1][0][0] = f[1][1][0] = f[1][0][1] = f[1][1][1] = 1;
for (i = 2; i <= n; ++i)
for (int p = 0; p < 2; ++p)
for (int q = 0; q < 2; ++q)
for (k = 1; k <= i; ++k) {
if (p == 1 && k == 1) continue ;
if (q == 1 && k == i) continue ;
LI ret = 1;
ret = f[k - 1][p][1] * f[i - k][1][q];
inc (ret);
f[i][p][q] += ret * c[i - 1][k - 1];
inc (f[i][p][q]);
}
//a[2] = 0;
//cout << (LL) calc();
//return 0;
//cout << (LL) f[2][1][0] << endl;
dfs (1, K);
puts ("-1");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3904kb
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: 3564kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3748kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'