# CCPC2022 Guilin J Permutation Puzzle

# 题意

有一个长度为 $n$ 的排列 $p$ ，其中的一些位置上的值未知。另有 $m$ 条约束关系 $(i,j)$ ，表示 $p_i\lt p_j$ 。求一种可能的满足所有约束的排列。

# 题解

这题目看起来就很典。

容易想到建图、正向拓扑、反向拓扑，得到每个位置取值的范围 $[l_i,r_i]$ 。接下来就更是经典问题，分配一些数字，使得每个位置的取值都满足相应范围。从小到大枚举还未分配的数字 $x$ ，这时候从所有未分配数字的、满足 $l_i\lt x$ 的位置中，选出 $r_i$ 最小的位置，分配这个 $x$ 。感性理解简易。小于 $x$ 的数字已经分配完，现在限定出 $l_i\lt x$ 这些可以分配但未分配的位置， $r_i$ 越小到后面越紧迫，所以优先满足。如果某一时刻， $x$ 没有可以分配的位置了，那就是一定无法满足所有约束。

哎，贪心，哎！

# 代码

	#include<cstdio>
	#include<queue>
	#include<vector>
	#include<functional>

	int read(){
	int out(0),c(getchar());
	for(;c<'0' \|\| c>'9';c=getchar());
	for(;c<='9' && c>='0';c=getchar())
	out=(out<<3)+(out<<1)+(c^48);
	return out;
	}

	inline void Min(int &a,const int &b){
	if(b<a) a=b;
	}

	inline void Max(int &a,const int &b){
	if(b>a) a=b;
	}

	const int MAXN=2e5+10;

	int T,N,M;
	int lv[MAXN],rv[MAXN];
	std::vector<int> to[MAXN],to2[MAXN];
	int id[MAXN],od[MAXN];
	int ans[MAXN];

	void topu(std::vector<int> to[],int dd[],int v[],std::function<void(int&,int)> op){
	static int d[MAXN];
	for(int i=1;i<=N;++i)
	d[i]=dd[i];
	std::queue<int> q;
	for(int i=1;i<=N;++i)
	if(!d[i])
	q.push(i);
	while(q.size()){
	int x=q.front();
	q.pop();
	for(int tt:to[x]){
	op(v[tt],v[x]);
	--d[tt];
	if(!d[tt])
	q.push(tt);
	}
	}
	}

	#define Return {printf("-1\n");return;}
	void work(){
	N=read(),M=read();
	for(int i=1;i<=N;++i){
	int x=read();
	if(x)
	lv[i]=rv[i]=x;
	else
	lv[i]=1,rv[i]=N;
	id[i]=od[i]=0;
	to[i].clear(),to2[i].clear();
	}
	for(int i=1;i<=M;++i){
	int x=read(),y=read();
	to[x].push_back(y);
	to2[y].push_back(x);
	++id[y],++od[x];
	}

	topu(to,id,lv,[](int &lv_tt,int lv_x){
	Max(lv_tt,lv_x+1);
	});
	topu(to2,od,rv,[](int &rv_tt,int rv_x){
	Min(rv_tt,rv_x-1);
	});
	for(int i=1;i<=N;++i)
	if(lv[i]>rv[i])
	Return;
	// for(int i=1;i<=N;++i)
	// printf("(%d %d) ",lv[i],rv[i]);
	// printf("\n");

	typedef struct{bool operator () (const int &a,const int &b)const{return rv[a]>rv[b];}} cmp;
	std::priority_queue<int,std::vector<int>,cmp> q;

	static int p[MAXN];
	for(int i=1;i<=N;++i)
	p[i]=i;
	std::sort(p+1,p+1+N,[](int a,int b){return lv[a]<lv[b];});
	int tp=1;

	for(int cur=1;cur<=N;++cur){
	while(tp<=N && lv[p[tp]]<=cur)
	q.push(p[tp++]);
	if(!q.size() \|\| rv[q.top()]<cur)
	Return;
	ans[q.top()]=cur;
	q.pop();
	}
	for(int i=1;i<=N;++i)
	printf("%d ",ans[i]);
	printf("\n");
	}
	int main(){
	T=read();
	while(T--){
	work();
	}
	}

拓扑排序贪心