QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #318042 | #7778. Turning Permutation | ucup_team_qiuly# | WA | 0ms | 3760kb | C++14 | 1.8kb | 2024-01-30 11:38:12 | 2024-01-30 11:38:12 |
Judging History
answer
#include <iostream>
#include <cstdio>
#define int long long
#define inf 1000000000000000000ll
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>inf/y)x=inf+1;
else x=min(inf+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=2;i<n;i++)
if (book[i]>0&&book[i-1]>0&&book[i+1]>0&&(book[i]-book[i-1])*(book[i]-book[i+1])<0)return 0;
for (int i=1;i<=n-2;i++)
if (book[i]>0&&book[i+1]>0&&book[i]<book[i+1]&&book[i+2]==0)return 0;
for (int i=3;i<=n;i++)
if (book[i]>0&&book[i-1]>0&&book[i]<book[i-1]&&book[i-2]==0)return 0;
for (int i=1;i<=n;i++){
if (book[i]!=0)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]=i;
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]=i;
}
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: 3612kb
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: 3668kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3616kb
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: 3684kb
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: 3728kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3672kb
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: 3760kb
input:
8 7
output:
1 3 5 2 4 7 6 8
result:
wrong answer 3rd numbers differ - expected: '2', found: '5'