QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293252#7778. Turning Permutationucup-team191#WA 0ms3680kbC++231.4kb2023-12-29 02:44:502023-12-29 02:44:50

Judging History

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

  • [2023-12-29 02:44:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3680kb
  • [2023-12-29 02:44:50]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=310,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int n;
ll k;
ll dp[N][N],cho[N][N],cn[N];
bool isk[N];

ll add(ll a,ll b)
{
	return min(LLINF,a+b);
}

ll mul(ll a,ll b)
{
	if (a>LLINF/b) return LLINF;
	return a*b;
}

int getk(int c)
{
	for (int i=0;;++i)
	{
		if (isk[i]) continue;
		if (c==0)
		{
			isk[i]=1;
			return i+1;
		}
		else --c;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for (int i=0;i<=n;++i)
	{
		cho[i][0]=1;
		for (int j=1;j<=i;++j) cho[i][j]=add(cho[i-1][j-1],cho[i-1][j]);
	}
	dp[1][0]=1;
	cn[1]=1;
	cn[0]=1;
	for (int i=2;i<=n;++i) for (int j=0;j<i;++j)
	{
		if (i%2)
		{
			for (int k=j;k<i-1;++k) dp[i][j]=add(dp[i][j],dp[i-1][k]);
		}
		else
		{
			for (int k=0;k<j;++k) dp[i][j]=add(dp[i][j],dp[i-1][k]);
		}
		cn[i]=add(cn[i],dp[i][j]);
	}
	--k;
	while (n)
	{
		bool isp=0;
		for (int p=0;p<n;++p)
		{
			ll kol=mul(cho[n-1][p],mul(cn[p],cn[n-1-p]));
			if (k>=kol)
			{
				k-=kol;
				continue;
			}
			cout<<getk(p)<<' ';
			isp=1;
			break;
		}
		if (!isp)
		{
			cout<<-1<<en;
			exit(0);
		}
		--n;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2

output:

2 1 3 

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

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

input:

3 1

output:

1 2 3 

result:

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