#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e5+5;
int n,k,a[mxn],par[mxn],ans=0,res[mxn],mx,dis[mxn],sz[mxn];
vector<int>v[mxn],state[mxn];
set<int>s;
set<pair<int,int>>tree;
bool mark[mxn];
void dfs(int z){
bool cnt=0;
for(auto i:v[z]){
if(par[z]!=i){
cnt=1;
dfs(i);
sz[z]++;
}
}
if(!cnt)s.insert(z);
}
void solve(int x=1){
if(x==n+1){
ans++;
return;
}
auto y=s.upper_bound(0);
while(y!=s.end()){
int z=*y;
s.erase(z);
sz[par[z]]--;
if(!sz[par[z]])
s.insert(par[z]);
solve(x+1);
s.insert(z);
sz[par[z]]++;
if(sz[par[z]])
s.erase(par[z]);
y=s.upper_bound(z);
if(ans==k){
res[z]=x;
break;
}
}
}
void make(int x,int y){
//cout<<x<<" "<<y<<'\n';
par[y]=x;
tree.insert({x,a[x]});
tree.insert({y,a[y]});
v[x].push_back(y);
v[y].push_back(x);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==-1){
state[n+1].push_back(i);
a[i]=n+1;
}
else{
state[a[i]].push_back(i);
mx=max(mx,a[i]);
}
}
assert(state[n+1].size());
if (state[n+1].size()){
cout<<-1;
return 0;
}
for(int i=1;i<state[n+1].size();i++){
make(state[n+1][i-1],state[n+1][i]);
}
tree.insert({state[n+1][0],n+1});
while(mx){
if(state[mx].size()==0){
cout<<-1;
return 0;
}
reverse(state[mx].begin(),state[mx].end());
for(auto i:state[mx]){
auto x=tree.lower_bound(make_pair(i,0));
if(x==tree.end()){
x--;
make(x->fr,i);
continue;
}
if(x==tree.begin()){
make(x->fr,i);
continue;
}
auto y=x;
y--;
if(x->sc>y->sc)
make(y->fr,i);
else if(x->sc<y->sc)
make(x->fr,i);
else{
if(y->sc==n+1)
make(x->fr,i);
else
make(y->fr,i);
}
}
mx--;
}
dfs(state[n+1][0]);
solve();
if(ans<k){
cout<<-1;
}
else{
for(int i=1;i<=n;i++){
cout<<res[i]<<" ";
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=1;i<state[n+1].size();i++){
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
