#include<bits/stdc++.h>
using namespace std;
#define MAXX 100007
#define MAXN 13
int b[MAXX],n,k;
struct perm
{
int ch[MAXN];
perm(int a[])
{
for (int q=1;q<=n;q++) ch[q]=a[q];
}
void show()
{
//cout<<"P:";
for (int q=1;q<=n;q++) cout<<ch[q]<<" ";
cout<<"\n";
}
};
vector<perm> ans;
int cur[MAXN],sb[MAXN];
bool dt[MAXN];
void check()
{
for (int q=1;q<=n;q++) sb[q]=-1;
for (int q=1;q<=n;q++) dt[q]=false;
for (int tm=1;true;tm++)
{
bool smyrt=false;
for (int q=1;q<=n;q++)
{
if (dt[q]) continue;
int next=q+1;
for (next=q+1;next<=n;next++)
{
if (!dt[next]) break;
}
if (next>n) break;
if (cur[next]>cur[q])
{
dt[q]=true;
smyrt=true;
sb[q]=tm;
}
}
if (!smyrt) break;
}
bool pr=true;
for (int q=1;q<=n;q++)
{
if (sb[q]!=b[q]) pr=false;
}
if (pr)
{
perm spr(cur);
ans.push_back(spr);
}
}
int ind[MAXN];
int ind2[MAXN];
bool cmp(perm &a, perm &b){
for (int q=1;q<=n;q++)
{
ind[a.ch[q]] = q;
ind2[b.ch[q]] = q;
}
for (int q=1;q<=n;q++)
{
if (ind[q] < ind2[q]) return 1;
if (ind[q] > ind2[q]) return 0;
}
return 0;
}
struct node
{
int sm;
int pos;
int lz;
} seg[4*MAXX];
void Initialise(int ind, int l, int r)
{
if (l==r)
{
if (b[l]==-1)
{
seg[ind].sm=n*2;
}
else
{
seg[ind].sm=b[l];
}
seg[ind].pos=l;
seg[ind].lz=0;
return;
}
int mid=(l+r)/2;
Initialise(ind*2,l,mid);
Initialise(ind*2+1,mid+1,r);
if (seg[ind*2].sm<=seg[ind*2+1].sm)
{
seg[ind].sm=seg[ind*2].sm;
seg[ind].pos=seg[ind*2].pos;
}
else
{
seg[ind].sm=seg[ind*2+1].sm;
seg[ind].pos=seg[ind*2+1].pos;
}
seg[ind].lz=0;
}
void Push(int ind, int l, int r)
{
if (seg[ind].lz==0) return;
seg[ind].sm-=seg[ind].lz;
if (l!=r)
{
seg[ind*2].lz+=seg[ind].lz;
seg[ind*2+1].lz+=seg[ind].lz;
}
seg[ind].lz=0;
}
void Update(int ind, int l, int r, int ql, int qr)
{
Push(ind,l,r);
if (l>=ql && r<=qr)
{
seg[ind].lz++;
Push(ind,l,r);
return;
}
int mid=(l+r)/2;
if (ql<=mid) Update(ind*2,l,mid,ql,qr);
if (qr>=mid+1) Update(ind*2+1,mid+1,r,ql,qr);
Push(ind*2,l,mid);
Push(ind*2+1,mid+1,r);
if (seg[ind*2].sm<=seg[ind*2+1].sm)
{
seg[ind].sm=seg[ind*2].sm;
seg[ind].pos=seg[ind*2].pos;
}
else
{
seg[ind].sm=seg[ind*2+1].sm;
seg[ind].pos=seg[ind*2+1].pos;
}
}
void UpdateCh(int ind, int l, int r, int pos)
{
Push(ind,l,r);
if (l==r && l==pos)
{
seg[ind].sm=n*2;
seg[ind].pos=l;
seg[ind].lz=0;
return;
}
int mid=(l+r)/2;
if (pos<=mid) UpdateCh(ind*2,l,mid,pos);
if (pos>=mid+1) UpdateCh(ind*2+1,mid+1,r,pos);
Push(ind*2,l,mid);
Push(ind*2+1,mid+1,r);
if (seg[ind*2].sm<=seg[ind*2+1].sm)
{
seg[ind].sm=seg[ind*2].sm;
seg[ind].pos=seg[ind*2].pos;
}
else
{
seg[ind].sm=seg[ind*2+1].sm;
seg[ind].pos=seg[ind*2+1].pos;
}
}
int ansk[MAXX];
int pr1[MAXX];
int main()
{
cin>>n>>k;
if (k!=1)
{
for (int q=1;q<=n;q++) cin>>b[q];
for (int q=1;q<=n;q++) cur[q]=q;
check();
while (next_permutation(cur+1,cur+n+1)) check();
sort(ans.begin(),ans.end(),cmp);
if (k<ans.size()) ans[k-1].show();
else cout<<"-1\n";
}
else
{
for (int q=1;q<=n;q++) cin>>b[q];
if (b[n]!=-1)
{
cout<<"-1\n";
return 0;
}
int br2=0;
for (int q=1;q<=n;q++)
{
if (b[q]!=-1) br2++;
}
pr1[0]=0;
for (int q=1;q<=n;q++)
{
if (b[q-1]==-1) pr1[q]=q-1;
else pr1[q]=pr1[q-1];
}
Initialise(1,1,n);
int tm=0;
for (tm=1;tm<n;tm++)
{
Push(1,1,n);
int sm=seg[1].sm;
int pos=seg[1].pos;
if (sm!=1) break;
ansk[pos]=tm;
UpdateCh(1,1,n,pos);
if (pos!=1) Update(1,1,n,pr1[pos]+1,pos-1);
}
if (tm-1 != br2)
{
cout<<"-1\n";
return 0;
}
tm=n;
for (int q=1;q<=n;q++)
{
if (ansk[q]==0)
{
ansk[q]=tm;
tm--;
}
cout<<ansk[q]<<" ";
}
cout<<"\n";
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:185:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<perm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | if (k<ans.size()) ans[k-1].show();
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
2600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
2600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
