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 fr first
#define sc second
#define ll long long
const int mxn=1e5+5;
int n,a[mxn],b[mxn],k,L[mxn],R[mxn],sz[mxn],mx[mxn];
vector<int>g[mxn],par[mxn];
set<int>s;
void solve(int m){
if(s.size()==0 && m<n+1){
cout<<-1;
exit(0);
}
if(m==n+1){
k--;
if(k==0){
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
exit(0);
}
return ;
}
vector<int>v;
for(auto i:s){
v.push_back(i);
if(v.size()==10)
break;
}
for(auto i:v){
a[i]=m;
s.erase(i);
for(auto j:par[i]){
sz[j]--;
if(sz[j]==0)
s.insert(j);
}
solve(m+1);
s.insert(i);
for(auto j:par[i]){
sz[j]++;
if(sz[j]==1)
s.erase(j);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
int cnt=0;
vector<int>hey;
for(int i=1;i<=n;i++){
cin>>b[i];
if(b[i]==-1)hey.push_back(i);
}
if(b[n]!=-1){
cout<<-1;
return 0;
}
for(int i=1;i<hey.size();i++){
par[hey[i]].push_back(hey[i-1]);
g[hey[i-1]].push_back(hey[i]);
}
for(int i=0;i<hey.size();i++){
int l=(i==0)?1:hey[i-1]+1;
vector<int>v;
for(int j=hey[i]-1;j>=l;j--){
par[j].push_back(hey[i]);
g[hey[i]].push_back(j);
R[j]=j+1;
while(R[j]<hey[i] && b[R[j]]<b[j]){
par[R[j]].push_back(j);
g[j].push_back(R[j]);
mx[j]=max(mx[j],b[R[j]]);
R[j]=R[R[j]];
}
par[j].push_back(R[j]);
g[R[j]].push_back(j);
if(mx[j]+1!=b[j]){
cout<<-1;
return 0;
}
}
}
for(int i=1;i<=n;i++){
sz[i]=g[i].size();
if(sz[i]==0)
s.insert(i);
}
solve(1);
cout<<-1;
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=1;i<hey.size();i++){
| ~^~~~~~~~~~~
Main.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=0;i<hey.size();i++){
| ~^~~~~~~~~~~
Main.cpp:55:6: warning: unused variable 'cnt' [-Wunused-variable]
55 | int cnt=0;
| ^~~
# | 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... |