QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623609 | #7778. Turning Permutation | foyonaczy | WA | 0ms | 3768kb | C++20 | 1.7kb | 2024-10-09 13:25:10 | 2024-10-09 13:25:11 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
constexpr int L = 0, R = 1;
i64 k, f[55][55][2];
int n;
int ans[55], p[55], tot;
bool solved = false;
i64 dfs(int pos, int prepos, int lr) {
if (pos > n) return 1;
if (~f[pos][prepos][lr])return f[pos][prepos][lr];
i64 res = 0;
if (p[pos]) {
int tmp = 0;
for (int i = 1; i <= p[pos]; i++)if (ans[i] <= pos)tmp++;
res += dfs(pos + 1, tmp, lr);
if (res > k)res = k + 1;
} else {
if ((lr ^ (pos % 2)) == L) {
for (int i = tot + 1; i <= prepos; i++) {
res += dfs(pos + 1, i, lr);
if (res > k)res = k + 1;
}
} else {
for (int i = prepos + 1; i <= pos; i++) {
res += dfs(pos + 1, i, lr);
if (res > k)res = k + 1;
}
}
}
f[pos][prepos][lr] = res;
return res;
}
void GetAns(int pos) {
tot++;
if (pos > n) {
solved = true;
for (int i = 1; i <= n; i++)std::cout << ans[i] << " ";
return;
}
for (int i = 1; i <= n; i++) {
if (p[i])continue;
p[i] = tot;
int tmp = tot == 1 ? i : ans[1];
i64 res;
memset(f, -1, sizeof(f));
res = dfs(2, 1, tmp % 2);
if (res >= k) {
ans[pos] = i;
GetAns(pos + 1);
return;
}
k -= res;
p[i] = 0;
}
}
void solve() {
memset(f, -1, sizeof(f));
std::cin >> n >> k;
GetAns(1);
if (!solved)std::cout << "-1\n";
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
int CZY = 1;
while (CZY--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3756kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
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: 3628kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3708kb
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: 0ms
memory: 3704kb
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: 3692kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
8 1
output:
1 3 2 5 4 7 6 8
result:
ok 8 numbers
Test #16:
score: -100
Wrong Answer
time: 0ms
memory: 3632kb
input:
8 7
output:
-1
result:
wrong answer 1st numbers differ - expected: '1', found: '-1'