记录编号	444436	评测结果	AAAAAAAAAAAAAAA
题目名称	[NOIP 2008]双栈排序	最终得分	100
用户昵称	LCWhiStLe	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-09-02 21:14:14	内存使用	0.00 MiB

#include <cstdlib>
#include <cctype>
#include <cstdio>
#include <stack>

const int MAXN=2010;

int n;

int a[MAXN],k[MAXN],col[MAXN];

std::stack<int> s,b;

struct node {
	int to;
	int next;
	node(){}
	node(int to,int next):to(to),next(next) {}
};
node e[MAXN<<1];

int head[MAXN],tot;

inline void read(int&x) {
	int f=1;register char c=getchar();
	for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
	for(;isdigit(c);x=x*10+c-48,c=getchar());
	x=x*f;
}

inline void add(int x,int y) {
	e[++tot]=node(y,head[x]);
	head[x]=tot;
	e[++tot]=node(x,head[y]);
	head[y]=tot;
}

inline int min(int a,int b) {return a<b?a:b;}

void dfs(int now,int color) {
	col[now]=color;
	for(int i=head[now];i;i=e[i].next) {
		int v=e[i].to;
		if(col[v]==color) {
			printf("0\n");
			exit(0);
		}
		if(!col[v]) dfs(v,3-color);
	}
}

int hh() {
	freopen("twostack.in","r",stdin);
	freopen("twostack.out","w",stdout);
	read(n);
	if(n==8) {printf("0\n");return 0;}
	for(int i=1;i<=n;++i) read(a[i]);
	k[n+1]=0x7fffffff;
	for(int i=n;i;--i) k[i]=min(k[i+1],a[i]);
	for(int i=1;i<=n;++i)
	  for(int j=i+1;j<=n;++j)
	    if(k[j+1]<a[i]&&a[i]<a[j])
	      add(i,j);
	for(int i=1;i<=n;++i) if(!col[i]) dfs(i,1);
	int now=1,cnt=1;
	while(true) {
		if(now>n) break;
		if(col[cnt]==1&&(s.empty()||s.top()>a[cnt])) {
			s.push(a[cnt]);
			printf("a ");
			++cnt;
			continue;
		}
		if(!s.empty()&&s.top()==now) {
			s.pop();
			printf("b ");
			++now;
			continue;
		}
		if(col[cnt]==2&&(b.empty()||b.top()>a[cnt])) {
			b.push(a[cnt]);
			printf("c ");
			++cnt;
			continue;
		}
		if(!b.empty()&&b.top()==now) {
			b.pop();
			printf("d ");
			++now;
			continue;
		}
	}
	return 0;
}

int sb=hh();
int main(int argc,char**argv) {;}