QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318038#7778. Turning Permutationucup_team_qiuly#WA 0ms3728kbC++141.4kb2024-01-30 11:23:502024-01-30 11:23:51

Judging History

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

  • [2024-01-30 11:23:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3728kb
  • [2024-01-30 11:23:50]
  • 提交

answer

#include <iostream>
#include <cstdio>
#define int long long
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>(k+1)/y)x=k+1;
	else x=min(k+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=1;i<=n;i++){
		if (book[i]==1)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]=1;
				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]=1;
	}
	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: 3604kb

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: 3596kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3656kb

input:

3 1

output:

1 2 3 

result:

wrong answer 2nd numbers differ - expected: '3', found: '2'