QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661886 | #7778. Turning Permutation | Minion | WA | 1ms | 7792kb | C++14 | 1.1kb | 2024-10-20 18:45:51 | 2024-10-20 18:45:52 |
Judging History
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'