#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e5+5;
int n, b[N], k, ans[N], d[N];
vector<int>g[N], nd;
bool mk[N];
struct seg_tree{
int sz, a[4*N];
seg_tree(){
sz=1;
while(sz<n)
sz<<=1;
for(int i=sz-1;i<sz+n-1;++i)
a[i]=1;
for(int i=sz-2;i>=0;--i)
a[i]=a[2*i+1]+a[2*i+2];
}
void zero(int x){
x+=sz-1;
a[x]=0;
while(x){
--x;
x/=2;
--a[x];
}
}
int sum(int x, int lx, int rx, int l, int r){
if(lx>=r || rx<=l)
return 0;
if(lx>=l && rx<=r)
return a[x];
int m=(lx+rx)/2;
return sum(2*x+1, lx, m, l, r)+sum(2*x+2, m, rx, l, r);
}
int nxt(int x, int lx, int rx, int h, int t){
if(lx==rx-1)
return lx;
int m=(lx+rx)/2;
if(h>=m)
return nxt(2*x+2, m, rx, h, t);
if(a[2*x+2]<t)
return nxt(2*x+1, lx, m, h, t-a[2*x+2]);
return nxt(2*x+2, m, rx, h, t);
}
int per(int x, int lx, int rx, int h, int t){
if(lx+1==rx)
return lx;
int m=(lx+rx)/2;
if(h<m)
return per(2*x+1, lx, m, h, t);
if(a[2*x+1]<t)
return per(2*x+2, m, rx, h, t-a[2*x+1]);
return per(2*x+1, lx, m, h, t);
}
int nxt(int x){
int t=sum(0, 0, sz, x+1, n);
if(t==0)
return -1;
return nxt(0, 0, sz, x, t);
}
int per(int x){
int t=sum(0, 0, sz, 0, x);
if(t==0)
return n;
return per(0, 0, sz, x, t);
}
};
void dfs(const int &v){
mk[v]=1;
for(int u: g[v]){
if(!mk[u])
dfs(u);
}
nd.push_back(v);
}
int main(){
cin>>n>>k;
for(int i=0;i<n;++i)
cin>>b[i];
if(b[n-1]!=-1){
cout<<-1<<'\n';
return 0;
}
if(n==1){
cout<<(k==1 ? 1 : -1)<<'\n';
return 0;
}
seg_tree A;
vector<int>v;
for(int i=0;i<n-1;++i){
if(b[i]==1){
g[i].push_back(i+1);
if(i!=0)
v.push_back(i-1);
A.zero(i);
}
else{
g[i+1].push_back(i);
}
}
for(int i=2;!v.empty();++i){
vector<int>w;
for(int u: v){
if(b[u]==i){
g[u].push_back(A.nxt(u));
A.zero(u);
int uw=A.per(u);
if(uw!=n)
w.push_back(uw);
}
else{
int uw=A.nxt(u);
if(uw!=-1)
g[uw].push_back(u);
}
}
v=w;
}
if(A.sum(0, 0, A.sz, 0, n)!=0){
cout<<-1<<'\n';
return 0;
}
for(int i=0;i<n;++i){
if(!mk[i])
dfs(i);
}
memset(mk, 0, sizeof(mk));
for(int u: nd){
mk[u]=1;
for(int w: g[u]){
if(!mk[w]){
cout<<-1<<'\n';
return 0;
}
}
}
priority_queue<int>pq;
for(int i=0;i<n;++i){
for(int u: g[i])
++d[u];
}
for(int i=0;i<n;++i){
if(d[i]==0){
pq.push(-i);
}
}
for(int i=0;i<n;++i){
int u=-pq.top();
pq.pop();
ans[u]=i;
for(int w: g[u]){
--d[w];
if(d[w]==0)
pq.push(-w);
}
}
for(int i=0;i<n;++i)
cout<<ans[i]+1<<' ';
cout<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
6096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
6096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
