记录编号	353120	评测结果	AAAAAAAAAAAAAAA
题目名称	[NOIP 2008]双栈排序	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-11-17 20:36:22	内存使用	3.93 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
const int N=1010;
int n,a[N],go[N][N],cnt[N];
int color[N];
void paint(int x,bool c){
	if (color[x]==-1){
		color[x]=c;
		for (int i=1;i<=cnt[x];i++) paint(go[x][i],!c);
	}
	else if (color[x]!=c)
		puts("0"),exit(0);
}
vector<int> ans;
stack<int> S[2];
void getin(int x){
	static int pos=1;
	bool check=1;
	vector<int> vec;
	while (check){
		check=0;
		if (!S[0].empty()&&S[0].top()==pos){
			S[0].pop();pos++;check=1;
			vec.push_back('b');
		}
		if (!S[1].empty()&&S[1].top()==pos){
			S[1].pop();pos++;check=1;
			vec.push_back('d');
		}
	}
	if (x+1<n&&!color[x+1]){
		for (int i=vec.size()-1;i>=0;i--)
		if (vec[i]=='b'){
			int len=(int)vec.size()-i-1;
			for (int k=pos-1;k>pos-1-len;k--)
				S[1].push(k);
			pos-=len;
			vec.resize((int)vec.size()-len);
			break;
		}
	}
	ans.insert(ans.end(),vec.begin(),vec.end());
}
int main()
{
	freopen("twostack.in","r",stdin);
	freopen("twostack.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int Min=1e9;
	for (int j=n;j;j--){
		for (int i=1;i<j;i++)
		if (a[i]<a[j]&&Min<a[i])
			go[i][++cnt[i]]=j,go[j][++cnt[j]]=i;
		Min=min(Min,a[j]);
	}
	for (int i=1;i<=n;i++) color[i]=-1;
	for (int i=1;i<=n;i++)
	if (color[i]==-1) paint(i,0);
	S[0].push(0);S[1].push(0);
	for (int id=1;id<=n;id++){
		if (!color[id]){
			S[0].push(a[id]);
			ans.push_back('a');
			getin(a[id]);
		}else
		if (color[id]){
			S[1].push(a[id]);
			ans.push_back('c');
			getin(a[id]);
		}
	}
	for (int i=0;i<(int)ans.size();i++)
		printf("%c ",ans[i]);
	puts("");
	return 0;
}