Submission #232722

#	Time	Username	Problem	Language	Result	Execution time	Memory
232722		medk	Building 4 (JOI20_building4)	C++14	100 / 100	470 ms	76952 KiB

building4

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

const int MAXN=5e5;
int n,tmp;

vector<vector<pair<int,int>>> a(2*MAXN);

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=0;i<2*n;i++)
    {
        cin>>tmp;
        a[i].pb({tmp,0});
    }
    for(int i=0;i<2*n;i++)
    {
        cin>>tmp;
        a[i].pb({tmp,1});
        if(a[i][0].x<a[i][1].x) swap(a[i][0],a[i][1]);
    }
    for(int i=2*n-2;i>=0;i--)
    {
        if(a[i][0].x>a[i+1][0].x) a[i].erase(a[i].begin());
        if(a[i][0].x>a[i+1][0].x) a[i].erase(a[i].begin());
        if(sz(a[i])==0)
        {
            cout<<-1;
            return 0;
        }
    }
    for(int i=1;i<2*n;i++)
        if(a[i].back().x<a[i-1].back().x) a[i].erase(prev(a[i].end()));
    string ans="";
    int cnt=0;
    for(int i=0;i<2*n;i++) ans+='A'+a[i][0].y, cnt+=a[i][0].y;
    int need=cnt<n;
    int left=abs(n-cnt), late=0;
    int newstart=0;
    for(int i=0;i<2*n && left;i++)
    {
        if(sz(a[i])!=2)
        {
            newstart=i+1;
            late=0;
            continue;
        }
        if(i) if(a[i][1].x>=a[i-1][0].x) newstart=i, late=0;
        if(a[i][1].y==need)
        {
            late++;
            if(late>=0)
            {
                for(int j=newstart;j<=i;j++) ans[j]='A'+a[j][1].y;
                newstart=i+1;
                left-=late;
                late=0;
            }
        }
        else late--;
    }
    if(left) cout<<-1;
    else cout<<ans;
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89