QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#278362 | #7778. Turning Permutation | ucup-team2303# | WA | 0ms | 3748kb | C++17 | 2.5kb | 2023-12-07 15:08:30 | 2023-12-07 15:08:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define PB emplace_back
#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define siz(a) ((int) a.size())
const int N = 50;
int a, b, s[N + 5], ans[N + 5], f[N + 5][N + 5], g[N + 5][N + 5], h[N + 5][2][2], C[N + 5][N + 5];
int calc() {
int now = 0, res = 1;
rep(l, 1, a) {
if(s[l]) continue;
int r = l;
while(r + 1 <= a && !s[r + 1]) ++r;
if((__int128) res * C[now + r - l + 1][now] > b) res = b + 1;
else res *= C[now + r - l + 1][now];
int tmp = h[r - l + 1][1][1];
if(l == 1) tmp += h[r - l + 1][0][1];
if(r == a) tmp += h[r - l + 1][1][0];
if(l == 1 && r == a) tmp += h[r - l + 1][0][0];
if((__int128) res * tmp > b) res = b + 1;
else res *= tmp;
now += r - l + 1;
l = r;
}
return res;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> a >> b;
rep(i, 0, a) {
C[i][0] = 1;
rep(j, 1, i) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
f[1][1] = g[1][1] = 1;
h[1][0][0] = h[1][1][1] = 1;
rep(i, 2, a) {
rep(j, 1, i) {
if(i & 1) {
rep(k, 1, j - 1) {
f[i][j] += f[i - 1][k];
f[i][j] = min(f[i][j], b + 1);
}
h[i][1][1] += f[i][j];
h[i][1][1] = min(h[i][1][1], b + 1);
}
else {
rep(k, j, i - 1) {
f[i][j] += f[i - 1][j];
f[i][j] = min(f[i][j], b + 1);
}
h[i][1][0] += f[i][j];
h[i][1][0] = min(h[i][1][0], b + 1);
}
if(i & 1) {
rep(k, j, i - 1) {
g[i][j] += g[i - 1][k];
g[i][j] = min(g[i][j], b + 1);
}
h[i][0][0] += g[i][j];
h[i][0][0] = min(h[i][0][0], b + 1);
}
else {
rep(k, 1, i - 1) {
g[i][j] += g[i - 1][j];
g[i][j] = min(g[i][j], b + 1);
}
h[i][0][1] += g[i][j];
h[i][0][1] = min(h[i][0][1], b + 1);
}
// f[i][j] = i & 1 ? f[i - 1][< j] : f[i - 1][>= j];
// g[i][j] = i & 1 ? g[i - 1][>= j] : f[i - 1][< j];
}
}
// s[a] = 1;
// cout << calc() << endl;
// return 0;
// cout << h[2][0][1] << endl;
rep(i, 1, a) {
bool is = 0;
rep(j, 1, a) if(!s[j]) {
s[j] = 1;
int tmp = calc();
// cout << i << ' ' << tmp << endl;
// rep(k, 1, a) cout << s[k] << " \n"[k == a];
if(b <= tmp) {
ans[i] = j;
is = 1;
break;
}
else {
b -= tmp;
s[j] = 0;
}
}
if(!is) return cout << -1, 0;
}
rep(i, 1, a) cout << ans[i] << ' ';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3748kb
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: 3736kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3684kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'