题解
令未给出的\(b_i=b_{i-1}+1\),模拟单调栈可得若干大小关系(若出栈则说明当前元素\(<\)栈顶元素,反之亦然)。若\(a_i>a_j\),则由\(i\)向\(j\)连一条有向边,拓扑排序可得出排序后的排列。易证边数\(\le 2n\),因此时间复杂度为\(O(nlogn)\)(\(p,x\)需自行排序)。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=3e6+10;
struct node {int x,y;} a[N];
int ans[N],st[N],top,in[N],n,k;
int fst[N],nxt[M],v[M],cnt;
bool vis[N];
queue<int> q;
bool cmp(node x,node y) {return x.x<y.x;}
void add(int x,int y)
{
v[++cnt]=y; in[y]++;
nxt[cnt]=fst[x],fst[x]=cnt;
}
void topo()
{
for(int i=1;i<=n;i++)
if(!in[i]) q.push(i);
while(!q.empty())
{
int x=q.front(); q.pop();
st[++top]=x;
for(int i=fst[x];i;i=nxt[i])
{
int y=v[i]; in[y]--;
if(!in[y]) q.push(y);
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++) {scanf("%d%d",&a[i].x,&a[i].y); vis[a[i].x]=1;}
for(int i=1;i<=n;i++)
if(!vis[i]) a[++k]=(node){i,0};
sort(a+1,a+k+1,cmp);
for(int i=1;i<=n;i++)
if(!vis[i]) a[i].y=a[i-1].y+1;
for(int i=1;i<=k;i++)
{
if(a[i].y>i || a[i-1].y+1<a[i].y) {printf("-1"); return 0;}
while(top>=a[i].y) {add(st[top],i); top--;}
add(i,st[top]); st[++top]=i;
}
top=0; topo();
if(top<n) {printf("-1"); return 0;}
for(int i=1;i<=top;i++) ans[st[i]]=n-i+1;
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}