QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546996#7778. Turning Permutationskc#WA 0ms3716kbC++141.6kb2024-09-04 16:37:492024-09-04 16:37:50

Judging History

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

  • [2024-09-04 16:37:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3716kb
  • [2024-09-04 16:37:49]
  • 提交

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'