QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#661886#7778. Turning PermutationMinionWA 1ms7792kbC++141.1kb2024-10-20 18:45:512024-10-20 18:45:52

Judging History

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

  • [2024-10-20 18:45:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7792kb
  • [2024-10-20 18:45:51]
  • 提交

answer

#include<cstdio>
#include<cstdlib>
#define fo(i,x,y) for(int i = x;i <= y;++i)
#define ll long long
#define N 10000010
#define mp 10000019
using namespace std;
int n,p[60];
ll f[N],s[N],k;int nxt[N],lst[mp],tot;
bool bz[N];
void ins(ll S,ll v) {s[++tot] = S,f[tot] = v,nxt[tot] = lst[S % mp],lst[S % mp] = tot;}
ll F(ll S)
{
	for(int i = lst[S % mp];i;i = nxt[i]) if(bz[i] == 0 && s[i] == S) return f[i];
	return -1;
}
void B(ll S) {for(int i = lst[S % mp];i;i = nxt[i]) if(bz[i] == 0 && s[i] == S) {bz[i] = 1;return;}}
ll dg(int x,ll S)
{
	if(x > n)
	{
		if(k == 0)
		{
			fo(i,1,n) printf("%d ",p[i]);
			exit(0);
		}
		return 1;
	}
	ll ff = F(S);
	if(~ff) return ff;
	ff = 0;
	fo(i,1,n)
	{
		if(S >> (i - 1) & 1) continue;
		bool bz = 1;
		if(i > 1 && i < n)
		{
			bool b1 = S >> i & 1,b2 = S >> (i - 2) & 1;
			if(b1 ^ b2) bz = 0;
		}
		if(bz)
		{
			p[x] = i;
			ll res = dg(x + 1,S | 1ll << (i - 1));
			if(ff + res > k) k -= ff,B(S | 1ll << (i - 1)),dg(x + 1,S | 1ll << (i - 1));
			else ff += res;
		}
	}
	return ins(S,ff),ff;
}
int main()
{
	scanf("%d%lld",&n,&k),--k;
	dg(1,0),puts("-1");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7792kb

input:

3 2

output:

2 3 1 

result:

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