This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |