Submission #1259125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259125		mohammadsam	Watermelon (INOI20_watermelon)	C++20	100 / 100	53 ms	25672 KiB

Main

/*
    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;
}

• Subtask 1: 7 / 7
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 18 / 18
• Subtask 5: 19 / 19