提交记录

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[1010],minn[1010],n,co[1010];
vector<int> b[1010];
queue<int> q;
stack<int> s1,s2;
void bfs(){
	co[1] = 1;
	q.push(1);
	while(q.empty() == false){
		int u = q.front(),size = b[u].size();
		for(int i = 0;i < size;i ++){
			int v = b[u][i];
			if(co[v] == 0){
				co[v] = 3 - co[u];
				q.push(v);
				continue;
			}
			if(co[u] != co[v]){
				continue;
			}
			cout << "0";
			exit(0);
		}
		q.pop();
	}
}
void print(){
	int t1 = N,t2 = N,num = 1,now = 1;
	while(num <= n){
		if(s1.empty() == false){
			t1 = s1.top();
		}
		if(s2.empty() == false){
			t2 = s2.top();
		}
		if(now <= n and (a[now] <= t1 or s1.empty() == true)){
			s1.push(a[now]);
			now ++;
			putchar('a');
			putchar(' ');
		}else if(t1 == num){
			s1.pop();
			num ++;
			putchar('b');
			putchar(' ');
		}else if(now <= n and (a[now] <= t2 or s2.empty() == true)){
			s2.push(a[now]);
			now ++;
			putchar('c');
			putchar(' ');
		}else if(t2 == num){
			s2.pop();
			num ++;
			putchar('d');
			putchar(' ');
		}
	}
}
int main(){
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> a[i]; 
	}
	minn[n + 1] = n + 1;
	for(int i = n;i >= 1;i --){
		minn[i] = min(minn[i + 1],a[i]);
	}
	for(int i = 1;i <= n;i ++){
		for(int j = i + 1;j <= n;j ++){
			if(minn[j + 1] < a[j] and a[i] < a[j]){
				b[i].push_back(j);
				b[j].push_back(i);
			}
		}
	}
	bfs();
	print();
	return 0;
}