QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482738 | #7778. Turning Permutation | _LAP_ | WA | 0ms | 3888kb | C++14 | 2.6kb | 2024-07-17 21:07:07 | 2024-07-17 21:07:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
const __int128 maxv = (long long)1e18 + 1;
int n; long long k;
long long f[N][3][3], binom[N][N];
// 0:= 无限制
// 1:= x < y
// 2:= x > y
set<int> Set;
inline long long check(int p) {
if(Set.count(p - 1) && !Set.count(p + 1) && p != n) return 0;
Set.insert(p);
vector<int> vec(Set.begin(), Set.end());
long long res = 1;
if(vec[0] != 1) res = min(maxv, (__int128)res * f[vec[0] - 1][0][1]);
for(int i = 1; i < vec.size(); i ++)
res = min(maxv, (__int128)res * f[vec[i] - vec[i - 1] - 1][2][1]);
if(vec.back() != n) res = min(maxv, (__int128)res * f[n - vec.back()][2][0]);
int lst = n - Set.size();
res = min(maxv, (__int128)res * binom[lst][vec[0] - 1]), lst -= vec[0] - 1;
for(int i = 1; i < vec.size(); i ++)
res = min(maxv, (__int128)res * binom[lst][vec[i] - vec[i - 1] - 1]), lst -= vec[i] - vec[i - 1] - 1;
res = min(maxv, (__int128)res * binom[lst][n - vec.back()]);
Set.erase(p);
return res;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> k;
binom[0][0] = 1;
for(int i = 1; i <= n; i ++) {
binom[i][0] = 1;
for(int j = 1; j <= i; j ++)
binom[i][j] = min((long long)maxv, binom[i - 1][j - 1] + binom[i - 1][j]);
}
for(int i = 0; i <= 2; i ++)
for(int j = 0; j <= 2; j ++)
f[1][i][j] = f[0][i][j] = 1;
for(int i = 2; i <= n; i ++) {
for(int a = 0; a <= 2; a ++) for(int b = 0; b <= 2; b ++) {
__int128 val = 0;
for(int x = 1; x <= i; x ++) {
if(a == 1 && x == 2) continue;
if(a == 2 && x == 1) continue;
if(b == 1 && x == i) continue;
if(b == 2 && x == i - 1) continue;
val += min(maxv, (__int128)f[x - 1][a][1] * f[i - x][2][b]) * binom[i - 1][x - 1];
val = min(val, maxv);
}
f[i][a][b] = val;
}
}
if(f[n][0][0] >= k) {
vector<int> ans;
for(int i = 1; i <= n; i ++) {
int x = 1;
while(true) {
while(Set.count(x)) x ++;
long long c = check(x);
if(c >= k) break;
else k -= c, x ++;
}
Set.insert(x);
ans.emplace_back(x);
}
for(int i = 0; i < ans.size(); i ++)
cout << ans[i] << " \n"[i + 1 == ans.size()];
} else cout << "-1" << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3852kb
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: 3588kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3848kb
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: 3648kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3620kb
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: 3888kb
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: 3588kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
8 1
output:
1 3 2 5 4 7 6 8
result:
ok 8 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
8 7
output:
1 3 2 5 7 8 4 6
result:
ok 8 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3632kb
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: 3688kb
input:
8 863
output:
3 2 7 5 1 6 8 4
result:
wrong answer 2nd numbers differ - expected: '5', found: '2'