Submission #635843

#	Time	Username	Problem	Language	Result	Execution time	Memory
635843		MohammadAghil	Watermelon (INOI20_watermelon)	C++17	100 / 100	287 ms	13804 KiB

Main

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pp;
 
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second
 
void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("inp.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
}

const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 20, inf = ll(1e9) + 5;

vector<int> adj[maxn];
int cnt[maxn], n;
 
int fen[maxn];
void upd(int i, int k){
    for(i++; i < maxn; i += i&-i) fen[i] = max(fen[i], k);
}
int get(int i){
    int res = 0;
    for(i++; i; i -= i&-i) res = max(res, fen[i]);
    return res;
}
vector<int> val(vector<int> p){
    vector<int> res(n);
    vector<int> stk;
    per(i,n-1,0){
        while(sz(stk) && p[stk.back()] < p[i]) stk.pop_back();
        if(sz(stk)){
            res[i] = get(stk.back()-1) + 1;
        }else res[i] = inf;
        upd(i, res[i]);
        stk.pb(i);
    }
    int tmp = n;
    rep(i,0,n) res[i] += res[i] == inf? tmp--: 0;
    return res;
}

vector<int> nxt(vector<int> p){
    vector<int> pos(n);
    rep(i,0,n) pos[p[i]] = i;
    rep(i,0,n) cnt[i] = 0;
    set<pp> s;
    int find = -1;
    per(i,n-1,0){
        s.insert({0, pos[i]});
        for(int c: adj[pos[i]]){
            s.erase(pp(cnt[c], c));
            s.insert(pp(++cnt[c], c));
        }
        auto it = s.upper_bound(pp(0, pos[i]));
        if(it != end(s) && it->ff == 0){
            find = i + 1;
            p[it->ss] = i;
            for(int c: adj[it->ss]){
                s.erase(pp(cnt[c], c));
                s.insert(pp(--cnt[c], c));
            }
            s.erase(it);
            break;
        }
    }
    if(find + 1){
        while(sz(s)){
            auto[_, r] = *begin(s);
            s.erase(begin(s));
            p[r] = find++;
            for(int c: adj[r]){
                s.erase(pp(cnt[c], c));
                s.insert(pp(--cnt[c], c));
            }     
        }
        return p;
    }
    return {};
}

int main(){ IOS();
    int k; cin >> n >> k;
    vector<int> a(n);
    int tmp = n;
    rep(i,0,n) {
        cin >> a[i];
        if(a[i] == -1){
            a[i] = inf + tmp, tmp--;
        }
    }

    vector<int> stk;
    rep(i,0,n){
        while(sz(stk) && a[stk.back()] < a[i]) stk.pop_back();
        if(sz(stk)){
            if(a[i] - a[stk.back()]){
                adj[i].pb(stk.back());
                cnt[stk.back()]++;
            } 
        }
        stk.pb(i);
    }
    stk.clear();
    per(i,n-1,0){
        while(sz(stk) && a[stk.back()] < a[i]) stk.pop_back();
        if(sz(stk)){
            adj[i].pb(stk.back());
            cnt[stk.back()]++;
        }
        stk.pb(i);
    }
    
    set<pp> s;
    rep(i,0,n) s.insert({cnt[i], i});
    vector<int> ans(n);
    int ptr = 0;
    while(sz(s) && begin(s)->ff == 0){
        auto[_, r] = *begin(s);
        s.erase(begin(s));
        ans[r] = ptr++;
        for(int c: adj[r]){
            s.erase(pp(cnt[c], c));
            s.insert(pp(--cnt[c], c));
        }
    }
    
    if(sz(s) || val(ans) != a){
        cout << -1 << '\n';
    } else{
        k--;
        while(k--){
            ans = nxt(ans);
            if(ans.empty()) return cout << -1 << '\n', 0;
        }
        rep(i,0,maxn) fen[i] = 0;
        if(val(ans) != a) cout << -1 << '\n';
        else for(int c: ans) cout << ++c << ' '; cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:161:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  161 |         else for(int c: ans) cout << ++c << ' '; cout << '\n';
      |         ^~~~
Main.cpp:161:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  161 |         else for(int c: ans) cout << ++c << ' '; cout << '\n';
      |                                                  ^~~~

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