QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#284265#7778. Turning Permutationiorit#WA 0ms4012kbC++142.3kb2023-12-16 13:06:532023-12-16 13:06:54

Judging History

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

  • [2023-12-16 13:06:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4012kb
  • [2023-12-16 13:06:53]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
#define sl(n) strlen(n)
#define endline puts("")
#define pii pair<int , int>
#define pr_q priority_queue
#define DEBUG puts("DEBUG.")
using namespace std;
const int N = 55 + 10;
const int inf = ~0u >> 2;
int n,p[N],q[N];
LL k,dp[N][N][2]; // dp x,y,0/1 表示剩了 x+y 个,比这一个数小、大的有 x,y 个,这一步向小 / 大走的 
bool vis[N];
LL C[N][N];
LL calc(int x)
{
	LL s = 1;
	for(int i = 1;i <= n;i++)
		q[i] = 0;
	for(int i = 1;i <= x;i++)
		q[ p[i] ] = i;
	int cnt = n - x;
	int lst = 0,dir = 0;
	bool fl = 0;
	q[0] = n + 1;
	for(int i = 1;i <= n;i++)
	{
		if( q[i] )
		{
			if(i == lst + 1)
			{
				if(fl)
				{
					fl = 0;
					dir = q[i] < q[lst] ? 0 : 1;
					goto bre;
				}
				if(!lst)
					goto bre;
				if(q[i] < q[lst] && !dir || q[i] > q[lst] && dir)
					return 0;
				dir ^= 1;
			}
			else
			{
				if(dir)
					return 0;
				if(lst && i % 2 != lst % 2)
					return 0;
				if((__int128)s * C[cnt][i - lst - 1] > 1e18)
					return 1000000000000000001;
				s *= C[cnt][i - lst - 1];
				if((__int128)s * dp[0][i - lst - 1][0] > 1e18)
					return 1000000000000000001;
				s *= dp[0][i - lst - 1][0];
				cnt -= i - lst - 1;
			}
			bre:;
			if(!lst)
				fl = 1;
			lst = i;
		}
	}
	if(cnt && dir)
		return 0;
	if(cnt)
	{
		if((__int128)s * dp[0][cnt][0] > 1e18)
			return 1000000000000000001;
		s *= dp[0][cnt][0];
	}
	return s;
}
int main()
{
	cin >> n >> k;
	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] + C[i - 1][j - 1];
	}
	for(int i = 1;i <= n;i++)
		dp[0][0][0] = dp[0][0][1] = 1;
	for(int sum = 1;sum <= n;sum++)
	{
		for(int x = 0;x <= sum;x++)
		{
			int y = sum - x;
			for(int xx = 0;xx <= x - 1;xx++)
				dp[x][y][1] += dp[xx][sum - 1 - xx][0];
			for(int yy = 0;yy <= y - 1;yy++)
				dp[x][y][0] += dp[sum - 1 - yy][yy][1];
		}
	}
	for(int i = 1;i <= n;i++)
	{
		bool fl = 0;
		for(int j = 1;j <= n;j++)
		{
			if( vis[j] )
				continue;
			p[i] = j;
			LL s = calc(i);
//			cout << i << " " << s << endl;
			if(k > s)
				k -= s;
			else
			{
				vis[j] = 1;
				fl = 1;
				break;
			}
		}
		if(!fl)
			return puts("-1"),0;
	}
	for(int i = 1;i <= n;i++)
		printf("%d " , p[i] );
	endline;
    return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3740kb

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: 0
Accepted
time: 0ms
memory: 3784kb

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 4012kb

input:

3 1

output:

1 3 2 

result:

ok 3 number(s): "1 3 2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3736kb

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

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

input:

5 85

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

5 846

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

5 6957

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

8 1

output:

1 3 2 5 4 7 6 8 

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

8 7

output:

1 3 2 5 7 8 4 6 

result:

ok 8 numbers

Test #17:

score: 0
Accepted
time: 0ms
memory: 3760kb

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

input:

8 863

output:

-1

result:

wrong answer 1st numbers differ - expected: '3', found: '-1'