QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#318038 | #7778. Turning Permutation | ucup_team_qiuly# | WA | 0ms | 3728kb | C++14 | 1.4kb | 2024-01-30 11:23:50 | 2024-01-30 11:23:51 |
Judging History
answer
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n,k,C[55][55],f[55][55][2];
int book[55],ans[55];
void mul(int &x,int y){
if (y==0)x=0;
else if (x>(k+1)/y)x=k+1;
else x=min(k+1,x*y);
return;
}
int calc(){
int ans=1;
int cnt=0;
for (int i=1;i<=n;i++)
if (book[i]==0)cnt++;
for (int i=1;i<=n;i++){
if (book[i]==1)continue;
int j=i;
while(j<n&&book[j+1]==0)j++;
mul(ans,C[cnt][j-i+1]);
cnt-=j-i+1;
if (i==1||j==n)mul(ans,f[0][j-i+1][1]);
else{
if ((j-i+1)&1)mul(ans,f[0][j-i+1][1]);
else ans=0;
}
i=j;
}
return ans;
}
signed main(){
cin>>n>>k;
f[0][0][0]=f[0][0][1]=1;
for (int t=0;t<=n;t++)
for (int i=0;i<=t;i++){
int j=t-i;
if (i==0&&j==0)continue;
for (int k=1;k<=i;k++){
f[i][j][0]+=f[k-1][i+j-k][1];
f[i][j][0]=min(f[i][j][0],k+1);
}
for (int k=1;k<=j;k++){
f[i][j][1]+=f[i+k-1][j-k][0];
f[i][j][1]=min(f[i][j][1],k+1);
}
}
for (int i=0;i<=n;i++)C[i][0]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
C[i][j]=min(k+1,C[i-1][j-1]+C[i-1][j]);
for (int i=1;i<=n;i++){
int p=-1;
for (int j=1;j<=n;j++)
if (book[j]==0){
book[j]=1;
int t=calc();
book[j]=0;
if (t<k)k-=t;
else{
p=j;
break;
}
}
if (p==-1){
cout<<-1<<endl;
return 0;
}
ans[i]=p;
book[p]=1;
}
for (int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3728kb
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: 3596kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3656kb
input:
3 1
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '3', found: '2'