Record in cf water question

CF1158C

Meaning: there are permutations P, making \ (nxt_i \) the first position on the right side of \ (p_i \) greater than \ (p_i \), if not \ (nxt_i=n+1 \)

Now that part of the whole p and nxt is lost, please construct a suitable p according to the remaining nxt and output any solution.

A sufficient and necessary condition for the existence of a solution is that \ (j\in(i,nex_i) \) satisfies \ (nex_j > nex_i \)

That is to say, for each \ (I \) direction \ (nxt_i \), one edge is connected, and then no two edges intersect

For point \ (i \) to \ (nex \) and the minimum j-connection satisfying \ (J < i \ \ wedge nex \ (J > nex \) to

So it's a topology

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define M 2100001
#define N 500010
using namespace std;

int n,m,k,a[N],d[M],s[N],ver[N],t[N],T,B;
queue<int> q;

void ins(int now,int l,int r,int k,int x)
{
    if(l==r)
    {
        d[now]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) ins(now*2,l,mid,k,x);
    else ins(now*2+1,mid+1,r,k,x);
    d[now]=1;
}

int ask(int now,int l,int r,int L)
{
    if(l==r) return d[now];
    int mid=(l+r)>>1, k=0;
    if(L<=mid && d[now*2]) k=ask(now*2,l,mid,L);
    if(!k)return ask(now*2+1,mid+1,r,L);
    return k;
}

void rb(int now,int l,int r)
{
    if(!d[now]) return ;
    d[now]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    rb(now*2,l,mid);
    rb(now*2+1,mid+1,r);
}

int main() 
{
    scanf("%d",&T);
    for(T;T;T--)
    {
        B=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&a[i]);
            if(a[i]==-1) a[i]=i+1;
        }
        
        for(int i=1;i<=n;i++)
        {
            k=ask(1,1,n+1,i+1);
            if(k && a[k]<a[i])  
            {
                B=1;
                break;
            }
            ins(1,1,n+1,i,a[i]);
            s[a[i]]++;
            if(!k) continue;
            ver[i]=k; s[k]++;
        }

        if(!B)
        {
            for(int i=1;i<=n;i++) if(!s[i]) q.push(i);
            k=0;
            while(q.size())
            {
                int x=q.front(); q.pop();
                s[ver[x]]--; s[a[x]]--;
                if(!s[ver[x]]) q.push(ver[x]);
                if(!s[a[x]]) q.push(a[x]);
                t[x]=++k;
            }
            if(k!=n+1) B=1;
        }
        
        if(B) printf("-1");
        else for(int i=1;i<=n;i++) printf("%d ",t[i]); 
        printf("\n");
        
        for(int i=1;i<=n+1;i++) t[i]=s[i]=ver[i]=a[i]=0;
        rb(1,1,n+1);
    }
}

Tags: Python

Posted on Tue, 05 Nov 2019 09:10:59 -0800 by chrisv