#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e5+5;
int n,k,a[mxn],ans=0,res[mxn],mx,dis[mxn],sz[mxn];
vector<int>v[mxn],state[mxn],par[mxn];
set<int>s;
set<int>tree;
bool mark[mxn];
void dfs(int z){
mark[z]=1;
sz[z]=v[z].size();
for(auto i:v[z]){
if(!mark[i])
dfs(i);
}
if(!v[z].size())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);
for(auto j:par[z]){
sz[j]--;
if(!sz[j])
s.insert(j);
}
solve(x+1);
s.insert(z);
for(auto j:par[z]){
sz[j]++;
s.erase(j);
}
if(ans==k){
res[z]=x;
break;
}
y=s.upper_bound(z);
}
}
void make(int x,int y){
//cout<<x<<" "<<y<<'\n';
par[y].push_back(x);
tree.insert(x);
tree.insert(y);
v[x].push_back(y);
}
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]);
}
}
if (!state[n+1].size() || state[n+1].back()!=n){
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]);
while(mx){
if(state[mx].size()==0){
cout<<-1;
return 0;
}
for(auto i:state[mx]){
tree.insert(i);
}
for(auto i:state[mx]){
auto x=tree.upper_bound(i);
if(x!=tree.end()){
int wtf=*x;
int f=0;
for(int j=i;j<wtf;j++){
if(a[j]==mx-1){
f=1;
}
}
if(f==0){
cout<<-1<<"\n";
exit(0);
}
make(*x,i);
}
x=tree.lower_bound(i);
if(x!=tree.begin()){
x--;
if(*x!=a[i])
make(*x,i);
}
}
mx--;
}
for(int i=1;i<=n;i++){
if(a[i]==n+1 || a[i]==1)continue;
bool rrr=0;
for(auto j:v[i]){
//cout<<j<<" ";
if(j==a[i]-1)rrr=1;
}//cout<<'\n';
if(!rrr){
cout<<-1;
return 0;
}
}
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:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=1;i<state[n+1].size();i++){
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
