Codeforces Round #584 Paint the Digits

原题链接：http://codeforces.com/contest/1209/problem/C

题目大意：给你一组数，你给标号，只能标为1或2，然后将标号为1的拿出来放在标号为2的左边，能形成一个上升序列。

因为每个数都是0-9，所以枚举0-9作为分界点

#include <bits/stdc++.h>
using namespace std;
char s[300000];
int a[300000];
int b[300000];
int e[300000];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>s;
        int a1,b1,flag=0;
        for(int k=0;k<10;k++)
        {
            int op,lpl=1;
            a1=0;b1=0;
            for(int i=0;i<n;i++)
            {
                op=(int)(s[i]-'0');
                if(op>k)
                {b[b1++]=op;
                e[i]=2;}
                if(op<k)
                {a[a1++]=op;
                e[i]=1;}
                if(op==k)
                {
                    if(b1==0)
                    {b[b1++]=op;
                    e[i]=2;
                    continue;}
                    if(op>=b[b1-1])
                    {b[b1++]=op;
                    e[i]=2;
                    continue;}
                    if(a1==0)
                    {a[a1++]=op;
                    e[i]=1;
                    continue;}
                    if(op>=a[a1-1])
                    {a[a1++]=op;
                    e[i]=1;
                    continue;}
                    if(op<b[b1-1]&&op<a[a1-1])
                    {lpl=0;
                        break;}
                }
            }
            if(lpl==1)
            {
                int fa=1,fb=1,fc=0;
                for(int i=0;i<a1-1;i++)
                {
                    if(a[i]>a[i+1])
                    {fa=0;
                    break;}
                }
                for(int i=0;i<b1-1;i++)
                {
                    if(b[i]>b[i+1])
                    {fb=0;
                    break;}
                }
                if(a1==0||b1==0)
                {fc=1;}
                if(a1>0&&b1>0){
                if(a[a1-1]<=b[b1-1])
                {fc=1;}}
                if(fa==1&&fb==1&&fc==1)
                {
                    flag=1;
                    for(int i=0;i<n;i++)
                    {cout<<e[i];}
                    cout<<endl;
                    break;
                }
            }
        }
        if(flag==0)
        {cout<<"-"<<endl;}
    }
}

123