QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546996 | #7778. Turning Permutation | skc# | WA | 0ms | 3716kb | C++14 | 1.6kb | 2024-09-04 16:37:49 | 2024-09-04 16:37:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 LLL;
const int N=55;
const LL inf=1LL<<62;
int n,a[N];
LL k,dp[N][2],C[N][N];
inline LL ADD(LL a,LL b){return a+b>inf?inf:a+b;}
inline LL MUL(LL a,LL b){
if(a>inf/b)return inf;
else return a*b;
}
LL calc(){
int cur1=0;
for(int i=1;i<=n;++i)if(a[i]==1){
cur1=!(i&1);
break;
}
int all=0,c=1;
for(int i=1;i<=n;++i)all+=!a[i];
int len=0;
for(int i=1;i<=n;++i)if(!a[i])++len;
else c=MUL(c,C[all][len]),all-=len,len=0;
for(int i=1,cur=cur1;i<n;++i,cur^=1)
if(a[i]&&a[i+1]&&((a[i]<a[i+1])==cur))return 0;
else if(a[i]&&!(a[i+1])&&cur)return 0;
len=0;
bool fst=1;
for(int i=1;i<=n;++i)if(!a[i])++len;
else{
if(!fst&&len%2==0&&len)return 0;
c=MUL(c,dp[len][fst?cur1:1]);
len=0;
fst=0;
}
c=MUL(c,dp[len][1]);
return c;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
dp[0][0]=dp[0][1]=1;
dp[1][0]=dp[1][1]=1;
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]=ADD(C[i-1][j],C[i-1][j-1]);
}
for(int i=1;i<=n;++i){
for(int p=1;p<=i;++p){
int cur=!(p&1);
dp[i][cur]=ADD(dp[i][cur],MUL(C[i-1][p-1],MUL(dp[p-1][cur],dp[i-p][1])));
}
}
if(ADD(dp[n][0],dp[n][1])<k)return cout<<"-1\n",0;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(a[j]==0){
a[j]=i;
LL way=calc();
// cerr<<"DEBUG"<<i<<' '<<j<<' '<<way<<endl;
if(k>way){k-=way;a[j]=0;}
else{
cout<<j<<" \n"[i==n];
break;
}
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
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: 3684kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 1
output:
1 3 2
result:
ok 3 number(s): "1 3 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 10
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
3 52
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
3 756
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 7721
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3648kb
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: 3628kb
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: 3716kb
input:
5 85
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 846
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 6957
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
8 1
output:
1 3 2 5 4 7 6 8
result:
ok 8 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
8 7
output:
1 3 2 5 7 8 4 6
result:
ok 8 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3644kb
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: 3644kb
input:
8 863
output:
3 2 5 4 7 6
result:
wrong answer 2nd numbers differ - expected: '5', found: '2'