QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#280581#7778. Turning Permutationucup-team1303#WA 1ms3836kbC++142.1kb2023-12-09 17:06:292023-12-09 17:06:29

Judging History

你现在查看的是最新测评结果

  • [2023-12-09 17:06:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3836kb
  • [2023-12-09 17:06:29]
  • 提交

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'