QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#290922 | #7778. Turning Permutation | yllcm | WA | 1ms | 3924kb | C++14 | 2.3kb | 2023-12-25 20:59:44 | 2023-12-25 20:59:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
#define int long long
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int INF = 1e18;
const int N = 55;
int n, k;
int f[N][N][2], g[N][2], C[N][N];
void init() {
C[0][0] = 1;
for(int i = 1; i < N; i++) {
C[i][0] = 1;
for(int j = 1; j <= i; j++) {
C[i][j] = min(INF + 1, C[i - 1][j] + C[i - 1][j - 1]);
}
}
f[1][1][0] = f[1][1][1] = 1;
for(int i = 2; i < N; i++) {
for(int j = 1; j <= i - 1; j++) {
for(int o = 0; o < 2; o++) {
for(int k = 1; k <= i; k++) {
if((o == 0 && k > j) || (o == 1 && k <= j))continue;
f[i][k][o] = min(INF + 1, f[i][k][o] + f[i - 1][j][o ^ 1]);
}
}
}
}
for(int i = 1; i < N; i++) {
for(int o = 0; o < 2; o++) {
for(int j = 1; j <= i; j++) {
g[i][o] = min(INF + 1, g[i][o] + f[i][j][o]);
}
}
}
return ;
}
int p[N], q[N];
int calc() {
int o = (p[1] & 1);
for(int i = 1; i < n; i++) {
if(!~q[i] || !~q[i + 1])continue;
if((q[i] > q[i + 1]) != ((i ^ p[1]) & 1))return 0;
}
int sum = 0, res = 1;
auto mul = [&](int x, int y) {return x && y && x > INF / y ? INF + 1 : x * y;};
for(int i = 1; i <= n; i++) {
if(~q[i])continue;
int k = i;
while(k < n && !~q[k + 1])k++;
res = mul(mul(res, g[k - i + 1][(i ^ p[1]) & 1]), C[sum + k - i + 1][sum]);
sum += k - i + 1; i = k;
}
return res;
}
signed main() {
init();
n = read(); k = read();
for(int i = 1; i <= n; i++)q[i] = -1;
int all = min(INF + 1, g[n][0] + g[n][1]);
if(all < k)return puts("-1"), 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(~q[j])continue;
p[i] = j; q[j] = i;
int val = calc();
if(val >= k)break;
else k -= val, q[j] = -1;
}
}
if(k > 1)return puts("-1");
for(int i = 1; i <= n; i++)printf("%lld ", p[i]); putchar('\n');
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3856kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3868kb
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: -100
Wrong Answer
time: 0ms
memory: 3924kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'