/*
in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;
#define File freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V) V.begin(),V.end()
#define setprec(x) fixed << setprecision(x)
#define Mp(a,b) make_pair(a,b)
#define len(V) (int)(V.size())
#define sep ' '
#define endl '\n'
#define pb push_back
#define fi first
#define sec second
#define popcount(x) __builtin_popcount(x)
#define lid u<<1
#define rid (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;
inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , k;
int arr[N];
vector<int> g[N];
int deg[N];
void add(int u,int v){
g[u].pb(v);
deg[v]++;
}
set<int> stk;
int ind[N];
int ans[N];
void solve(int i){
if( i == n+1){
k--;
if(k == 0){
for(int i=1;i<=n;i++) ans[ind[i]] = i;
for(int i =1 ;i <=n ;i++) cout << ans[i] << sep;
cout << endl;
exit(0);
}
return;
}
if(stk.empty()){
cout << -1 << endl;
exit(0);
}
int h = *stk.begin();
while(true){
stk.erase(h);
ind[i] = h;
for(auto x : g[h]){
deg[x]--;
if(deg[x] == 0) stk.insert(x);
}
solve(i+1);
for(auto x : g[h]){
if(deg[x] == 0) stk.erase(x);
deg[x]++;
}
stk.insert(h);
auto it = stk.upper_bound(h);
if(it == stk.end()) break;
h = *it;
}
}
int R[N];
int32_t main() {
ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
cin >> n >> k ;
for(int i=1 ;i <=n ;i++) cin >> arr[i];
int mx = *max_element(arr+1,arr+n+1);
if(mx == -1){
if(k == 1) {
for(int i=1;i<=n;i++) cout << n - i + 1 << sep;
cout << endl;
}
else cout << -1 << endl;
return 0;
}
if(arr[n] != -1) assert(0);
mx++;
for(int i =1 ;i <=n ;i++){
if(arr[i] == -1) arr[i] = mx;
}
for(int i = n ; i >= 1;i--){
for(R[i] = i + 1;R[i]<=n and arr[R[i]] < arr[i];R[i] = R[R[i]]);
if(arr[i] != mx) add(i,R[i]);
}
vector<int> S;
for(int i =n ;i >= 1;i--){
int x = 0;
while(!S.empty() and arr[S.back()] <= arr[i]) {
if(arr[S.back()] < arr[i]){
add(S.back(),i);
x = max(x,arr[S.back()]);
}
S.pop_back();
}
if(i != n and x < (arr[i] - 1)){
if(arr[i] != mx){
cout << -1 << endl;
return 0;
}
add(R[i],i);
}
S.pb(i);
}
int lst = -1;
for(int i = n;i >= 1;i--){
if(arr[i] == mx){
if(lst != -1) add(lst,i);
lst = i;
}
}
for(int i =1 ;i <= n;i++){
if(deg[i] == 0) stk.insert(i);
}
solve(1);
cout << -1 << endl;
return 0;
}
# | 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... |