# 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;
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++)
{
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