QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#280581 | #7778. Turning Permutation | ucup-team1303# | WA | 1ms | 3836kb | C++14 | 2.1kb | 2023-12-09 17:06:29 | 2023-12-09 17:06:29 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define mk make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
#define i128 __int128
const int N=55;
const ll INF=2e18;
ll dp[N][N],f[N],C[N][N];
int n,cur[N],p[N];
void add(ll &x,ll v){x+=v;if(x>=INF)x=INF;}
ll mul(ll x,ll v){x=((i128)x)*((i128)v);if(x>=INF)x=INF;}
ll cmod(ll x){return min(x,INF);}
signed main(void){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
#endif
n=read();ll k=read();
dp[1][1]=1,f[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(i&1)for(int k=1;k<j;k++)add(dp[i][j],dp[i-1][k]);
else for(int k=j;k<=i-1;k++)add(dp[i][j],dp[i-1][k]);
add(f[i],dp[i][j]);
}
}
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]=C[i-1][j],add(C[i][j],C[i-1][j-1]);
}
if(k>cmod(f[n]+f[n]))return puts("-1"),0;
// for(int i=1;i<=n;i++)cout<<f[i]<<" ";puts("");
for(int i=1;i<=n;i++)cur[i]=n+1;
auto calc=[&](){
int A=0,B=0;
// cout<<"calc cur = ";for(int i=1;i<=n;i++)cout<<cur[i]<<" ";puts("");
bool chk=0;
for(int i=1;i<=n;i++)chk|=(cur[i]!=n+1);
if(chk==0)return cmod(f[n]+f[n]);
for(int i=1;i<n;i++){
if(i&1)A|=(cur[i]<cur[i+1]),B|=(cur[i]>cur[i+1]);
else A|=(cur[i]>cur[i+1]),B|=(cur[i]<cur[i+1]);
}
if(A&&B)return 0ll;
ll res=1;int lst=0;
vector<int>vals;
for(int i=1;i<=n;i++)if(cur[i]!=n+1)vals.emplace_back(i-lst-1),lst=i;
vals.emplace_back(n-lst);
int sum=0;
for(int x:vals)if(x!=0)res=mul(res,f[x]),res=mul(res,C[x+sum][x]),sum+=x;
// cout<<"res = "<<res<<endl;
return res;
};
vector<int>vis(n+1,0);
for(int i=1;i<=n;i++){
// cout<<"i = "<<i<<endl;
for(int j=1;j<=n;j++)if(!vis[j]){
cur[j]=i;ll cnt=calc();
// cout<<"try p "<<i<<" <- "<<j<<" cnt = "<<cnt<<" k = "<<k<<endl;
if(k<=cnt){vis[j]=1,p[i]=j;break;}
else k-=cnt,cur[j]=n+1;
}
}
for(int i=1;i<=n;i++)cout<<p[i]<<" ";puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3544kb
input:
4 6
output:
0 2 1 4
result:
wrong answer 1st numbers differ - expected: '3', found: '0'