#include<bits/stdc++.h>
using namespace std;
#define MAXX 100007
#define MAXN 13
int b[MAXX],b2[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;
}
int ansk[MAXX];
int pr1[MAXX];
int chb[MAXX];
int posOfLST[MAXX];
int bfMe[MAXX];
bool finalcheck()
{
stack<pair<int,int>> st;
chb[n]=-1;
//if (chb[n]!=b[n]) return false;
st.push({ansk[n],n});
for (int q=n-1;q>=1;q--)
{
chb[q]=-2;
while (true)
{
if (st.empty())
{
chb[q]=-1;
st.push({ansk[q],q});
break;
}
int chislo = st.top().first;
int pos = st.top().second;
if (ansk[q]>chislo)
{
chb[q]=max(chb[q],chb[pos]);
st.pop();
continue;
}
if (chb[q]==-2) chb[q]=1;
else chb[q]++;
st.push({ansk[q],q});
break;
}
//cout<<q<<":"<<chb[q]<<" "<<b[q]<<"\n";
//if (chb[q]!=b[q]2) return false;
}
for (int q=1;q<=n;q++)
{
if (chb[q]!=b2[q]) return false;
}
return true;
}
int lf[MAXN],rf[MAXN];
void getSecond()
{
int lst=0;
for (int q=1;q<=n;q++)
{
if (b[q]==-1)
{
lf[q]=lst;
}
if (b[q]==1)
{
lst=q;
}
}
lst=0;
for (int q=n;q>=1;q--)
{
if (b[q]==-1)
{
rf[q]=lst;
}
if (b[q]==1)
{
lst=q;
}
}
int pos=0;
for (int q=1;q<=n;q++)
{
if (lf[q]!=0)
{
pos=q;
break;
}
}
if (pos==0)
{
cout<<"-1\n";
return;
}
if (b[n-1]==-1)
{
int ch=ansk[n];
int hpos=0;
for (int q=1;q<=n;q++)
{
if (ansk[q]==ch-1)
{
hpos=q;
}
}
swap(ansk[hpos],ansk[n]);
for (int q=1;q<=n;q++)
{
cout<<ansk[q]<<" ";
}
cout<<"\n";
return;
}
}
int main()
{
cin>>n>>k;
if (k!=1 && k!=2 || true)
{
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";
return 0;
}
if (k==1)
{
for (int q=1;q<=n;q++) cin>>b[q];
for (int q=1;q<=n;q++) b2[q]=b[q];
int br2=0;
for (int q=1;q<=n;q++)
{
if (b[q]!=-1) br2++;
}
if (b[n]==-1) posOfLST[n+2]=n;
else posOfLST[b[n]]=n;
for (int q=n-1;q>=1;q--)
{
if (b[q]==-1) continue;
if (b[q]==1) {posOfLST[b[q]]=q;continue;}
int pos=posOfLST[b[q]-1];
if (pos==0)
{
cout<<"-1\n";
return 0;
}
if (bfMe[pos]!=0)
{
cout<<"-1\n";
return 0;
}
bfMe[pos]=q;
posOfLST[b[q]]=q;
}
int dok=1;
for (int q=1;q<=n;q++)
{
if (b[q]==1)
{
ansk[q]=dok;
//cout<<q<<" "<<dok<<"\n";
dok++;
int w=bfMe[q];
while (w!=0)
{
ansk[w]=dok;
//cout<<w<<" "<<dok<<"\n";
dok++;
w=bfMe[w];
}
}
}
int tm=n;
for (int q=1;q<=n;q++)
{
if (ansk[q]==0)
{
ansk[q]=tm;
tm--;
}
}
if (finalcheck())
{
for (int q=1;q<=n;q++)
{
cout<<ansk[q]<<" ";
}
cout<<"\n";
}
else
{
cout<<"-1\n";
}
}
else
{
for (int q=1;q<=n;q++) cin>>b[q];
for (int q=1;q<=n;q++) b2[q]=b[q];
int br2=0;
for (int q=1;q<=n;q++)
{
if (b[q]!=-1) br2++;
}
if (b[n]==-1) posOfLST[n+2]=n;
else posOfLST[b[n]]=n;
for (int q=n-1;q>=1;q--)
{
if (b[q]==-1) continue;
if (b[q]==1) {posOfLST[b[q]]=q;continue;}
int pos=posOfLST[b[q]-1];
if (pos==0)
{
cout<<"-1\n";
return 0;
}
if (bfMe[pos]!=0)
{
cout<<"-1\n";
return 0;
}
bfMe[pos]=q;
posOfLST[b[q]]=q;
}
int dok=1;
for (int q=1;q<=n;q++)
{
if (b[q]==1)
{
ansk[q]=dok;
//cout<<q<<" "<<dok<<"\n";
dok++;
int w=bfMe[q];
while (w!=0)
{
ansk[w]=dok;
//cout<<w<<" "<<dok<<"\n";
dok++;
w=bfMe[w];
}
}
}
int tm=n;
for (int q=1;q<=n;q++)
{
if (ansk[q]==0)
{
ansk[q]=tm;
tm--;
}
}
if (finalcheck())
{
getSecond();
}
else
{
cout<<"-1\n";
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:182:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
182 | if (k!=1 && k!=2 || true)
| ~~~~~^~~~~~~
Main.cpp:189:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<perm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | if (k<ans.size()) ans[k-1].show();
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
33 ms |
320 KB |
Output is correct |
3 |
Correct |
418 ms |
760 KB |
Output is correct |
4 |
Correct |
375 ms |
308 KB |
Output is correct |
5 |
Correct |
369 ms |
288 KB |
Output is correct |
6 |
Correct |
31 ms |
212 KB |
Output is correct |
7 |
Correct |
364 ms |
292 KB |
Output is correct |
8 |
Correct |
386 ms |
296 KB |
Output is correct |
9 |
Correct |
38 ms |
296 KB |
Output is correct |
10 |
Correct |
33 ms |
320 KB |
Output is correct |
11 |
Correct |
3 ms |
212 KB |
Output is correct |
12 |
Correct |
395 ms |
488 KB |
Output is correct |
13 |
Correct |
384 ms |
604 KB |
Output is correct |
14 |
Correct |
390 ms |
332 KB |
Output is correct |
15 |
Correct |
375 ms |
460 KB |
Output is correct |
16 |
Correct |
362 ms |
428 KB |
Output is correct |
17 |
Correct |
381 ms |
408 KB |
Output is correct |
18 |
Correct |
33 ms |
340 KB |
Output is correct |
19 |
Correct |
363 ms |
212 KB |
Output is correct |
20 |
Correct |
379 ms |
300 KB |
Output is correct |
21 |
Correct |
367 ms |
316 KB |
Output is correct |
22 |
Correct |
367 ms |
308 KB |
Output is correct |
23 |
Correct |
365 ms |
340 KB |
Output is correct |
24 |
Correct |
388 ms |
320 KB |
Output is correct |
25 |
Correct |
378 ms |
300 KB |
Output is correct |
26 |
Correct |
372 ms |
296 KB |
Output is correct |
27 |
Correct |
382 ms |
304 KB |
Output is correct |
28 |
Correct |
433 ms |
300 KB |
Output is correct |
29 |
Correct |
387 ms |
432 KB |
Output is correct |
30 |
Correct |
5 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
212 KB |
Output is correct |
32 |
Correct |
3 ms |
212 KB |
Output is correct |
33 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
33 ms |
320 KB |
Output is correct |
3 |
Correct |
418 ms |
760 KB |
Output is correct |
4 |
Correct |
375 ms |
308 KB |
Output is correct |
5 |
Correct |
369 ms |
288 KB |
Output is correct |
6 |
Correct |
31 ms |
212 KB |
Output is correct |
7 |
Correct |
364 ms |
292 KB |
Output is correct |
8 |
Correct |
386 ms |
296 KB |
Output is correct |
9 |
Correct |
38 ms |
296 KB |
Output is correct |
10 |
Correct |
33 ms |
320 KB |
Output is correct |
11 |
Correct |
3 ms |
212 KB |
Output is correct |
12 |
Correct |
395 ms |
488 KB |
Output is correct |
13 |
Correct |
384 ms |
604 KB |
Output is correct |
14 |
Correct |
390 ms |
332 KB |
Output is correct |
15 |
Correct |
375 ms |
460 KB |
Output is correct |
16 |
Correct |
362 ms |
428 KB |
Output is correct |
17 |
Correct |
381 ms |
408 KB |
Output is correct |
18 |
Correct |
33 ms |
340 KB |
Output is correct |
19 |
Correct |
363 ms |
212 KB |
Output is correct |
20 |
Correct |
379 ms |
300 KB |
Output is correct |
21 |
Correct |
367 ms |
316 KB |
Output is correct |
22 |
Correct |
367 ms |
308 KB |
Output is correct |
23 |
Correct |
365 ms |
340 KB |
Output is correct |
24 |
Correct |
388 ms |
320 KB |
Output is correct |
25 |
Correct |
378 ms |
300 KB |
Output is correct |
26 |
Correct |
372 ms |
296 KB |
Output is correct |
27 |
Correct |
382 ms |
304 KB |
Output is correct |
28 |
Correct |
433 ms |
300 KB |
Output is correct |
29 |
Correct |
387 ms |
432 KB |
Output is correct |
30 |
Correct |
5 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
212 KB |
Output is correct |
32 |
Correct |
3 ms |
212 KB |
Output is correct |
33 |
Correct |
3 ms |
332 KB |
Output is correct |
34 |
Execution timed out |
2078 ms |
320 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2060 ms |
624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2060 ms |
624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
33 ms |
320 KB |
Output is correct |
3 |
Correct |
418 ms |
760 KB |
Output is correct |
4 |
Correct |
375 ms |
308 KB |
Output is correct |
5 |
Correct |
369 ms |
288 KB |
Output is correct |
6 |
Correct |
31 ms |
212 KB |
Output is correct |
7 |
Correct |
364 ms |
292 KB |
Output is correct |
8 |
Correct |
386 ms |
296 KB |
Output is correct |
9 |
Correct |
38 ms |
296 KB |
Output is correct |
10 |
Correct |
33 ms |
320 KB |
Output is correct |
11 |
Correct |
3 ms |
212 KB |
Output is correct |
12 |
Correct |
395 ms |
488 KB |
Output is correct |
13 |
Correct |
384 ms |
604 KB |
Output is correct |
14 |
Correct |
390 ms |
332 KB |
Output is correct |
15 |
Correct |
375 ms |
460 KB |
Output is correct |
16 |
Correct |
362 ms |
428 KB |
Output is correct |
17 |
Correct |
381 ms |
408 KB |
Output is correct |
18 |
Correct |
33 ms |
340 KB |
Output is correct |
19 |
Correct |
363 ms |
212 KB |
Output is correct |
20 |
Correct |
379 ms |
300 KB |
Output is correct |
21 |
Correct |
367 ms |
316 KB |
Output is correct |
22 |
Correct |
367 ms |
308 KB |
Output is correct |
23 |
Correct |
365 ms |
340 KB |
Output is correct |
24 |
Correct |
388 ms |
320 KB |
Output is correct |
25 |
Correct |
378 ms |
300 KB |
Output is correct |
26 |
Correct |
372 ms |
296 KB |
Output is correct |
27 |
Correct |
382 ms |
304 KB |
Output is correct |
28 |
Correct |
433 ms |
300 KB |
Output is correct |
29 |
Correct |
387 ms |
432 KB |
Output is correct |
30 |
Correct |
5 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
212 KB |
Output is correct |
32 |
Correct |
3 ms |
212 KB |
Output is correct |
33 |
Correct |
3 ms |
332 KB |
Output is correct |
34 |
Execution timed out |
2078 ms |
320 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |