[NOIP2008]双栈排序

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=1000+7;
int n,val[N],minx[N],col[N];
bool flag;
vector<int> p[N];
void init(){
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	minx[n+1]=n+1;
	for(int i=n;i>=1;i--)
		minx[i]=min(minx[i+1],val[i]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(val[i]<val[j]&&minx[j+1]<val[i]) p[i].push_back(j),p[j].push_back(i);
}
void run(){
	for(int i=1;i<=n;i++)
		if(!col[i]){
			queue<int> q;
			col[i]=1;
			q.push(i);
			while(!q.empty()){
				int u=q.front();
				q.pop();
				for(int j=0;j<p[u].size();j++){
					int v=p[u][j];
					if(col[v]){
						if(col[v]==col[u]){
							flag=1;
							return;
						}
						continue;
					}
					col[v]=3-col[u];
					q.push(v);
				}
			}
		}
}
struct stack{
	int a[N],p=0;
	int top(){ return a[p]; }
	bool empty(){ return p==0; }
	void pop(){ if(p) p--;}
	void push(int x){ a[++p]=x; }
}s[3];
int now;
bool judge(int id){
	if(s[id].empty()||s[id].top()!=now+1) return 0;
	return 1;
}
void Pop(int id){
	now++;
	s[id].pop();
	putchar(id==1 ?'b' :'d');
	putchar(' ');
}
void Push(int v,int id){
	if(id==2) while(judge(1)) Pop(1);
	while(!s[id].empty()&&s[id].top()<v){
		if(!judge(id)) Pop(3-id);
		else Pop(id);
	}
	if(id==2) while(judge(1)) Pop(1);
	s[id].push(v);
	putchar(id==1 ?'a' :'c');
	putchar(' ');
}
void print(){
	for(int i=1;i<=n;i++){
		Push(val[i],col[i]);
	}
	while(!s[1].empty()){
		if(!judge(1)) Pop(2);
		else Pop(1);
	}
	while(!s[2].empty()) Pop(2);
}
int main(){
	init();
	run();
	if(flag){
		printf("0");
		return 0;
	}
	print();
	return 0;
}