subject

A very mellow topic

Problem solution

The key to this problem is to analyze whether two numbers can be on the same stack

According to this logic, the general idea of this topic is:

If a number xxx, 111~(x − 1)(x-1)(x − 1) has been popped up, then xxx will pop up, otherwise xxx will remain in the stack, and all subsequent numbers larger than him cannot enter the stack. If a number yyy wants to enter and finds that the top of both stacks is smaller than him, then this method will not work.

So I < J, AI < Aji < J, a_ {i}<a_ {j} When I < J, AI < AJ ， I, Ji, Ji and J can be on the same stack.

So for I < J, AI < Aji < J, a_ {i}<a_ {j} When can I < J, AI < AJ be on the same stack? It is said that the order of stacks decreases, so how can it be on the same stack? The only case is that iii has been out of the stack before jjj enters.

But if there is a number after jjj than aia_{i}ai: I can't do it when I'm young?

So when I < J < K, AK < AI < Aji < J < K, a_ {k}<a_ {i}<a_ {j} When I < J < K, AK < AI < AJ ， I, Ji, Ji and j cannot be on the same stack.

At this time, we just need to connect the edges of two points that cannot be on the same stack, and then if there are odd rings, we can't, just a graph with even rings? That's a bipartite graph, so at this time, we just need to use bipartite graph coloring to judge whether it is a bipartite graph.

Bipartite graph coloring?

In fact, it is to choose a random point, paint it red, and then choose the edge adjacent to him, paint it blue, and so on.

If you find a point with two colors, you can't.

Finally, as long as the simulated two points on different sides can no longer be in the stack.

code

#include<cstdio>
#include<cstring>
#define  M  2100000
#define  N  1100
using  namespace  std;
struct  node
{
	int  x,y,next;
}tr[M];int  len,last[N];
inline  void  ins(int  x,int  y)
{
	len++;tr[len].x=x;tr[len].y=y;tr[len].next=last[x];last[x]=len;
}
int  col[N],n,a[N],li[2][N];
char  st[2100];int  cnt;
int  f[N];
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
void  dp()//Figure out which two positions cannot be on the same stack 
{
	f[n]=a[n];
	for(int  i=n-1;i>=1;i--)f[i]=mymin(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])
			{
				ins(i,j);ins(j,i);
			}
		}
	}
}
bool  color(int  x,int  u)//Bipartite graph coloring 
{
	col[x]=u;
	for(int  k=last[x];k;k=tr[k].next)
	{
		int  y=tr[k].y;
		if(col[x]==col[y])return  false;
		if(!col[y]  &&  !color(y,3-u))return  false;
	}
	return  true;
}
int  main()
{
	int  T;scanf("%d",&T);
	while(T--)
	{
		cnt=0;li[0][0]=0;li[1][0]=0;
		len=0;memset(last,0,sizeof(last));
		scanf("%d",&n);
		for(int  i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			col[i]=0;
		}
		dp();
		bool  bk=true;
		for(int  i=1;i<=n;i++)
		{
			if(!col[i]  &&  !color(i,1)){bk=false;break;}
		}
		if(bk==false)
		{
			printf("0\n");
			continue;
		}
		int  top=1;
		for(int  i=1;i<=n;i++)//Simulate inbound sort 
		{
			int  j=col[i]-1;
			st[++cnt]=j==0?'a':'c';
			li[j][++li[j][0]]=a[i];
			while(li[0][li[0][0]]==top  ||  li[1][li[1][0]]==top)
			{
				if(li[0][li[0][0]]==top)st[++cnt]='b',li[0][0]--,top++;//Out of stack 
				else  if(li[1][li[1][0]]==top)st[++cnt]='d',li[1][0]--,top++;//Out of stack 
			}
		}
		for(int  i=1;i<(n<<1);i++)printf("%c ",st[i]);
		printf("%c\n",st[(n<<1)]);
	}
	return  0;
}