Submission #635389

#	Time	Username	Problem	Language	Result	Execution time	Memory
635389		Mahdi	Watermelon (INOI20_watermelon)	C++17	31 / 100	111 ms	10164 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e5+5;
int n, b[N], k, ans[N], d[N];
vector<int>g[N], nd;
bool mk[N];

struct seg_tree{
    int sz, a[4*N];
    seg_tree(){
        sz=1;
        while(sz<n)
            sz<<=1;
        for(int i=sz-1;i<sz+n-1;++i)
            a[i]=1;
        for(int i=sz-2;i>=0;--i)
            a[i]=a[2*i+1]+a[2*i+2];
    }

    void zero(int x){
        x+=sz-1;
        a[x]=0;
        while(x){
            --x;
            x/=2;
            --a[x];
        }
    }

    int sum(int x, int lx, int rx, int l, int r){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return a[x];
        int m=(lx+rx)/2;
        return sum(2*x+1, lx, m, l, r)+sum(2*x+2, m, rx, l, r);
    }
    
    int nxt(int x, int lx, int rx, int h, int t){
        if(lx==rx-1)
            return lx;
        int m=(lx+rx)/2;
        if(h>=m)
            return nxt(2*x+2, m, rx, h, t);
        if(a[2*x+2]<t)
            return nxt(2*x+1, lx, m, h, t-a[2*x+2]);
        return nxt(2*x+2, m, rx, h, t);
    }
    
    int per(int x, int lx, int rx, int h, int t){
        if(lx+1==rx)
            return lx;
        int m=(lx+rx)/2;
        if(h<m)
            return per(2*x+1, lx, m, h, t);
        if(a[2*x+1]<t)
            return per(2*x+2, m, rx, h, t-a[2*x+1]);
        return per(2*x+1, lx, m, h, t);
    }

    int nxt(int x){
        int t=sum(0, 0, sz, x+1, n);
        if(t==0)
            return -1;
        return nxt(0, 0, sz, x, t);
    }

    int per(int x){
        int t=sum(0, 0, sz, 0, x);
        if(t==0)
            return n;
        return per(0, 0, sz, x, t);
    }
};

void dfs(const int &v){
    mk[v]=1;
    for(int u: g[v]){
        if(!mk[u])
            dfs(u);
    }
    nd.push_back(v);
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;++i)
        cin>>b[i];
    int cmo=0;
    for(int i=0;i<n;++i){
        if(b[i]==-1)
            ++cmo;
    }
    if(b[n-1]!=-1){
        cout<<-1<<'\n';
        return 0;
    }
    if(n==1){
        cout<<(k==1 ? 1 : -1)<<'\n';
        return 0;
    }
    seg_tree A;
    vector<int>v;
    for(int i=0;i<n-1;++i){
        if(b[i]==1){
            g[i].push_back(i+1);
            int pp=A.per(i);
            if(pp!=n)
                v.push_back(pp);
            A.zero(i);
        }
        else{
            g[i+1].push_back(i);
        }
    }
    for(int i=2;!v.empty();++i){
        v.resize(distance(v.begin(), unique(all(v))));
        vector<int>w;
        for(int u: v){
            if(b[u]==i){
                g[u].push_back(A.nxt(u));
                A.zero(u);
                int uw=A.per(u);
                if(uw!=n)
                    w.push_back(uw);
            }
            else{
                int uw=A.nxt(u);
                if(uw!=-1)
                    g[uw].push_back(u);
            }
        }
        v=w;
    }
    if(A.sum(0, 0, A.sz, 0, n)!=cmo){
        cout<<-1<<'\n';
        return 0;
    }
    for(int i=0;i<n;++i){
        if(!mk[i])
            dfs(i);
    }
    memset(mk, 0, sizeof(mk));
    for(int u: nd){
        mk[u]=1;
        for(int w: g[u]){
            if(!mk[w]){
                cout<<-1<<'\n';
                return 0;
            }
        }
    }
    priority_queue<int>pq;
    for(int i=0;i<n;++i){
        for(int u: g[i])
            ++d[u];
    }
    for(int i=0;i<n;++i){
        if(d[i]==0){
            pq.push(-i);
        }
    }
    for(int i=0;i<n;++i){
        int u=-pq.top();
        pq.pop();
        ans[u]=i;
        for(int w: g[u]){
            --d[w];
            if(d[w]==0)
                pq.push(-w);
        }
    }
    for(int i=0;i<n;++i)
        cout<<ans[i]+1<<' ';
    cout<<'\n';
}

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