QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #290035 | #7778. Turning Permutation | willow# | WA | 1ms | 3944kb | C++14 | 2.5kb | 2023-12-24 10:11:29 | 2023-12-24 10:11:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
const int N = 55;
const LL M = 2e18;
int n; LL K;
int pos[N], ans[N], fix[N];
LL dp[N][N];
LL Count(int t) { //t = 0: 1 2; t = 1: 2 1
memset(dp, 0, sizeof(dp));
if (t == 0) {
if (pos[1] && pos[2] && pos[1] > pos[2]) return 0;
if (pos[2] == 1) return 0;
dp[2][2] = 1;
} else {
if (pos[1] && pos[2] && pos[1] < pos[2]) return 0;
if (pos[1] == 1) return 0;
dp[2][1] = 1;
}
int tot = (pos[1] > 0) + (pos[2] > 0);
for (int i = 3; i <= n; ++i, t ^= 1) { //t = 0: pos[i] < pos[i - 1] t = 1: pos[i] > pos[i - 1]
int tmp = 1;
if (pos[i]) {
for (int j = 1; j < i; ++j) {
tmp += (pos[j] && pos[j] < pos[i]);
}
}
for (int j = 1; j < i; ++j) {
LL val = dp[i - 1][j];
if (!val) continue;
if (pos[i]) {
int k = tmp;
if (t == 0 && k <= j) {
dp[i][k] = min(M, dp[i][k] + val);
}
if (t == 1 && k > j) {
dp[i][k] = min(M, dp[i][k] + val);
}
} else {
for (int k = tot + 1; k <= i; ++k) {
if (t == 0 && k <= j) {
dp[i][k] = min(M, dp[i][k] + val);
}
if (t == 1 && k > j) {
dp[i][k] = min(M, dp[i][k] + val);
}
}
}
}
tot += (pos[i] > 0);
}
LL ret = 0;
for (int j = 1; j <= n; ++j) {
ret = min(M, ret + dp[n][j]);
}
return ret;
}
void solve() {
scanf("%d %lld", &n, &K);
for (int i = 1; i <= n; ++i) {
//cerr << K << endl;
bool flag = 0;
for (int j = 1; j <= n; ++j) {
if (pos[j]) continue;
pos[j] = i;
LL tmp = Count(0) + Count(1);
//cerr << i << ' ' << j << ' ' << tmp << endl;
if (tmp < K) {
K -= tmp;
pos[j] = 0;
} else {
//cerr << i << ' ' << j << endl;
ans[i] = j;
flag = 1;
break;
}
}
if (!flag) {
puts("-1");
return;
}
}
for (int i = 1; i <= n; ++i) {
printf("%d ", ans[i]);
}
printf("\n");
}
int main() {
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3944kb
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: 3744kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
5 1
output:
1 3 2 5 4
result:
ok 5 number(s): "1 3 2 5 4"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
5 8
output:
2 4 1 3 5
result:
ok 5 number(s): "2 4 1 3 5"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
8 1
output:
1 3 2 5 4 7 6 8
result:
ok 8 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
8 7
output:
1 3 2 5 7 8 4 6
result:
ok 8 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
8 71
output:
1 3 7 5 4 2 6 8
result:
ok 8 numbers
Test #18:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
8 863
output:
-1
result:
wrong answer 1st numbers differ - expected: '3', found: '-1'