[luogu1155 NOIP2008] 双栈排序 (二分图染色)

传送门

Description

Input

第一行是一个整数 n 。

第二行有 n 个用空格隔开的正整数，构成一个 1−n 的排列。

Output

共一行，如果输入的排列不是“可双栈排序排列”，输出数字 0 ；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

Sample Input

输入样例#1：

4
1 3 2 4

输入样例#2：

4
2 3 4 1

输入样例#3：

3
2 3 1

Sample Output

输出样例#1：

a b a a b b a b

输出样例#2：

0

输出样例#3：

a c a b b d

Solution

将不可能在同一个栈的两个数连边，二分图染色（为使字典序最小优先放1栈即可qwq）

Code

//By Menteur_Hxy
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define R(i,a,b) for(register int i=(b);i>=(a);i--)
#define E(i,u) for(register int i=head[u],v;i;i=nxt[i])
#define ins(a,b) add(a,b),add(b,a)
#define add(a,b) nxt[++cnt]=head[a],to[cnt]=b,head[a]=cnt
using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x*f;
}

const int N=1010;
int n,cnt,now;
int nxt[N*N],to[N*N],head[N];
int da[N],col[N],sta[2][N],top[2],f[N];

void dfs(int u) {
	E(i,u) if(col[(v=to[i])]==-1) col[v]=col[u]^1,dfs(v);
		else if(col[v]==col[u]) {puts("0");exit(0);}
}

int main() {
	n=read();
	F(i,1,n) da[i]=read(); f[n]=da[n];
	R(i,1,n-1) f[i]=min(f[i+1],da[i]);
	F(i,1,n) F(j,i+1,n) if(da[i]<da[j]&&da[i]>f[j]) ins(i,j);
	memset(col,-1,sizeof(col));
	F(i,1,n) if(col[i]==-1) col[i]=0,dfs(i);
	now=1;
	F(i,1,n) {
		int c=col[i]; sta[c][++top[c]]=da[i];
		printf("%c ",(c?'c':'a'));
		while(sta[0][top[0]]==now||sta[1][top[1]]==now) {
			if(sta[0][top[0]]==now) top[0]--,printf("b ");
			else top[1]--,printf("d ");
			now++;
		}
	}
	return 0;
}