// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5+7;
int n,k , a[maxn],in[maxn],np=0;
vector<int> e[maxn];
vector<int> val(maxn),out(maxn);
set<int> source;
void permut
(int q)
{
if (source.empty())
{
if (++np == k) out = val;
return;
}
vector<int> sou;
int sz = 0;
for (auto v : source)
{
if (sz < 10)
sou.push_back(v) , sz++;
else break;
}
for (auto v : sou)
{
source.erase(v);
val[v] = q;
for (auto to : e[v])
if (--in[to] == 0)
source.insert(to);
permut(q+1);
if (np >= k) return;
val[v] = 0;
source.insert(v);
for (auto to : e[v])
if (++in[to] == 1)
source.erase(to);
}
}
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i=1; i<=n; i++)
cin >> a[i];
if (a[n] != -1)
{
cout << -1 << '\n';
return 0;
}
vector<int> st;
st.push_back(n);
bool eraser = true;
for (int i=n-1; i; i--)
{
int dp = 0;
if (a[i] == -1)
{
while(!st.empty())
{
int v = st.back();
e[v].push_back(i); in[i]++;
st.pop_back();
}
st.push_back(i);
continue;
}
while (!st.empty())
{
int v = st.back();
if (a[v] == -1 or a[v] >= a[i])
{
if (a[i] != dp+1)
eraser = false;
e[i].push_back(v);
st.push_back(i); in[v]++;
break;
}
else if (a[v] > dp)
{
dp = a[v];
e[v].push_back(i);
in[i]++;
}
st.pop_back();
}
st.push_back(i);
}
if (!eraser)
{
cout << -1 << '\n';
return 0;
}
vector<int> val(maxn);
for (int i=1; i<=n; i++)
if (!in[i]) source.insert(i);
permut(1);
if (np < k)
{
cout << -1 << '\n';
return 0;
}
for (int i=1; i<=n; i++)
cout << out[i] << ' ';
cout << '\n';
}
# | 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... |