Description

nodgd的粉絲太多了，每天都會有很多人排隊要簽名。
今天有n個人排隊，每個人的身高都是一個整數，且互不相同。很不巧，nodgd今天去忙別的事情去了，就只好讓這些粉絲們明天再來。同時nodgd提出了一個要求，每個人都要記住自己前面與多少個比自己高的人，以便于明天恢復到今天的順序。
但是，粉絲們或多或少都是有些失望的，失望使她們暈頭轉向、神魂顛倒，已經分不清楚哪一邊是“前面”了，于是她們可能是記住了前面比自己高的人的個數，也可能是記住了后面比自己高的人的個數，而且他們不知道自己記住的是哪一個方向。
nodgd覺得，即使這樣明天也能恢復出一個排隊順序，使得任意一個人的兩個方向中至少有一個方向上的比他高的人數和他記住的數字相同。可惜n比較大，顯然需要寫個程序來解決，nodgd很忙，寫程序這種事情就交給你了。

Input

第一行輸入一個整數n，表示指令的條數。
接下來n行，每行兩個整數ai,bi，表示一個人的身高和她記住的數字，保證身高互不相同。

Output

輸出一行，這個隊列里從前到后的每個人的身高。如果有多個答案滿足題意，輸出字典序最小。如果不存在滿足題意的排列，輸出“impossible”（不含引號）。

Sample Input

輸入1：

4
4 1
3 1
6 0
2 0

輸入2：

6
1 5
8 0
3 1
4 0
2 0
6 0

Sample Output

輸出1：

2 4 3 6

輸出2：

1 2 4 3 6 8

Data Constraint

對于 40% 的數據：N≤10
對于 60% 的數據：N≤1000
對于 100% 的數據：N≤100000

Hint

【樣例解釋1】
在所給出的答案隊列中，第一個人身高為2，前面有0個人比他高，所以他是輸入的第4個人；第二個人身高為4，右邊有1個人比他高，所以他是輸入的第1個人；第三個人身高為3，右邊有1個人比他高，所以他是輸入的第2個人；第四個人身高為6，左邊有0個人比他高，所以他是輸入的第3個人。
顯然，如果排列為“6 3 4 2”也是滿足題意的，但是字典序不是最小的。

Solution

• 我們可以按高度從大到小排一遍序，倒著處理。

• 設當前做到第 i 個人，前 i?1 個人（排好序了）到已經站好了。

• 我們操作時保證滿足條件，為了滿足字典序最小，那么填的位置 k 肯定是滿足：k=Min{bi+1,i?1?bi}

• 即在往后看和往前看中選一個較小的填進去，最后輸出排好的序列即可。

• 其中的插入操作可以用線段樹的二分查找、或者Splay維護。

• 我用的是 Splay ，時間復雜度為 O(N?log?N) ，代碼如下：

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=1e5+3,inf=1e9; struct data {int x,y; }a[N]; int root,tot; int fa[N],size[N],key[N],s[N][2]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int min(int x,int y) {return x<y?x:y; } inline bool cmp(data x,data y) {return x.x>y.x; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline void update(int x) {size[x]=size[s[x][0]]+size[s[x][1]]+1; } inline void newnode(int &v,int val,int p) {v=++tot;fa[v]=p,size[v]=1,key[v]=val;s[v][0]=s[v][1]=0; } inline void rotate(int x) {int y=fa[x],w=pd(x);if(s[y][w]=s[x][w^1]) fa[s[x][w^1]]=y;if(fa[x]=fa[y]) s[fa[y]][pd(y)]=x;s[fa[y]=x][w^1]=y;update(y); } inline void splay(int x,int k) {for(int y;(y=fa[x])^k;rotate(x))if(fa[y]^k) rotate(pd(x)==pd(y)?y:x);update(x);if(!k) root=x; } inline int kth(int x,int k) {if(size[s[x][0]]+1==k) return x;if(k<=size[s[x][0]]) return kth(s[x][0],k);return kth(s[x][1],k-size[s[x][0]]-1); } inline void print(int x) {if(s[x][0]) print(s[x][0]);if(key[x]<inf) write(key[x]),putchar(' ');if(s[x][1]) print(s[x][1]); } int main() {int n=read();for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++)if(a[i].y>i-1) return 0&puts("impossible");newnode(root,inf,0);newnode(s[root][1],inf,root);update(root);for(int i=1;i<=n;i++){int k=min(a[i].y,(size[root]-2)-a[i].y)+1;splay(kth(root,k),0);splay(kth(root,k+1),root);newnode(s[s[root][1]][0],a[i].x,s[root][1]);update(s[root][1]),update(root);}print(root);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5456. 【NOIP2017提高A组冲刺11.6】奇怪的队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。