记录编号	315087	评测结果	AAAAAAAAAAAAAAA
题目名称	[NOIP 2008]双栈排序	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2016-10-04 18:07:38	内存使用	8.11 MiB

/*
  Name: [NOIP2008] 双栈排序 
  Copyright: Cydia 
  Author: Yuhang li 
  Date: 04/10/16 17:05
  Description: 二分图染色 + 模拟 
*/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>

using namespace std;

const int maxn=1000+10;

stack<int> q1,q2;

int len,N;

int head[maxn],A[maxn],f[maxn],colr[maxn];

struct edge
{
       int to,next;
}e[maxn*maxn];

void ADD(int x,int y)
{
     len++;
     e[len].to=y;
     e[len].next=head[x];
     head[x]=len;
}
void dfs(int x,int c)
{
    // puts("OK");
    colr[x]=c;
    for(int t,i=head[x];i;i=e[i].next)
    {
            t=e[i].to;
            if(!colr[t])dfs(t,3-c);
            if(colr[t]==c)
            {
                 printf("0");
                 exit(0);
            }
    }
}

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]);
    f[N+1]=0x7ffffff;//puts("OK");
    for(int i=N;i>=1;i--)f[i]=min(f[i+1],A[i]);
    for(int i=1;i<N;i++)
    {
            for(int j=i+1;j<=N;j++)
            {
                    if(A[i]<A[j]&&f[j+1]<A[i])
                    {
                    ADD(i,j),ADD(j,i);  
                    }
            }
    }
    for(int i=1;i<=N;i++)
    if(!colr[i])dfs(i,1);
    int tim=1;
    for(int i=1;i<=N;i++)
    {
      if(colr[i]==1)q1.push(A[i]),printf("a ");
      else q2.push(A[i]),printf("c ");
      while(!q1.empty()&&q1.top()==tim)
      {
      q1.pop();printf("b "); tim++;
      }
      while(!q2.empty()&&q2.top()==tim)
      {
       q2.pop();printf("d ");tim++;
      }
    }
    while(!q1.empty()&&q1.top()==tim)
      {
      q1.pop();printf("b "); tim++;
      }
      while(!q2.empty()&&q2.top()==tim)
      {
       q2.pop();printf("d ");tim++;
      }
    fclose(stdin);
    fclose(stdout);
    return 0;
}