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 FOR(i, a, b) for (int i = (a); i < (b); i++)
#define int int64_t
const int64_t INF = 1ll << 60;
const int N = 1e5 + 5;
int b[N], in[N], nx[N], n, k, a[N];
vector<int> adj[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
assert(k == 1);
FOR(i, 0, n) {
cin >> b[i];
b[i] = (b[i] == -1 ? INF : b[i]);
}
vector<int> st;
for (int i = n - 1; i >= 0; i--) {
while (st.size() && b[st.back()] < b[i]) st.pop_back();
if (st.size() && b[i] != INF) {
adj[i].push_back(st.back());
in[st.back()]++;
}
st.push_back(i);
}
for (int i = n - 1; i >= 0; i--) {
if (b[i] == INF) {
FOR(j, i + 1, n) {
adj[j].push_back(i);
in[i]++;
if (b[j] == INF)
break;
}
}
else {
if (nx[b[i] - 1]) {
FOR(j, i + 1, nx[b[i] - 1] + 1) {
adj[j].push_back(i);
in[i]++;
}
}
else if (b[i] > 1) {
cout << -1;
return 0;
}
nx[b[i]] = i;
}
}
/*
FOR(i, 0, n) {
for (auto u: adj[i])
cout << i << ' ' << u << endl;
cout << endl;
}
*/
set<int> S;
FOR(i, 0, n)
if (!in[i])
S.insert(i);
FOR(i, 1, n + 1) {
if (S.empty()) {
cout << -1;
return 0;
}
int x = *S.begin();
a[x] = i;
S.erase(S.begin());
for (auto u: adj[x]) {
in[u]--;
if (!in[u])
S.insert(u);
}
}
FOR(i, 0, n)
cout << a[i] << ' ';
cout << endl;
}
//11:28:05
# | 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... |