QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721696 | #7778. Turning Permutation | louhao088 | WA | 0ms | 3752kb | C++23 | 2.5kb | 2024-11-07 16:38:20 | 2024-11-07 16:38:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lowbit(i) (i&(-i))
#define fi first
#define se second
#define pi pair<int,int>
#define int long long
const int inf=1e18,maxn=105,M=100005;
inline int read(){
char ch=getchar();int x=0;bool f=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f==1)x=-x;return x;
}
int n,k,T,x,y,res=0,a[maxn];
int C[maxn][maxn],f[maxn],g[maxn][maxn],ans[maxn];
bool solve(int x){
int sum=1,s=0;
double g=0,h=log(1e18);
for(int i=1;i<=n;i++){
if(!a[i])s++;
else if(s){
if(s%2==0&&s!=i-1)return 0;
s=0;
}
}s=0;
for(int i=1;i<=n;i++){
if(a[i])s++;
else if(s){
if(s%2==0)return 0;
s=0;
}
}
s=0;
for(int i=1;i<=n;i++){
if(!a[i])s++;
else if(s){
g=g+log(C[x][s])+log(f[s]);
if(g>h)return 1;
sum=sum*f[s]*C[x][s];
x-=s;
s=0;
}
}
if(s){
g=g+log(C[x][s])+log(f[s]);
if(g>h)return 1;
sum=sum*f[s]*C[x][s];
}
//cout<<sum<<" "<<x<<endl;
if(sum>=k)return 1;
else {
k-=sum;
return 0;
}
}
signed main(){
n=read(),k=read();C[0][0]=1;
for(int i=1;i<=n;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<=i;j++){
C[i][j]=C[i-1][j-1]+C[i-1][j];
if(C[i][j]>inf)C[i][j]=inf;
//cout<<C[i][j]<<" "<<i<<" "<<j<<endl;
}
}g[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++){
g[i][j]+=g[i-1][k];
g[i][j]=min(g[i][j],inf);
}
}
else {
for(int k=j;k<i;k++){
g[i][j]+=g[i-1][k];
g[i][j]=min(g[i][j],inf);
}
}
f[i]+=g[i][j];
f[i]=min(f[i],inf);
}//cout<<f[i]<<" ";
}//scout<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!a[j]){
a[j]=i;
if(solve(n-i))break;
if(j==n){puts("-1");exit(0);}
a[j]=0;
}
}
}
for(int i=1;i<=n;i++)ans[a[i]]=i;
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3752kb
input:
3 2
output:
2 3 1
result:
wrong answer 2nd numbers differ - expected: '1', found: '3'