Submission #1291497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291497		simona1230	Building 4 (JOI20_building4)	C++20	0 / 100	4 ms	576 KiB

building4

#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],b[1000001];
int lf[1000001][2],rt[1000001][2];

void read()
{
    cin>>n;
    for(int i=1;i<=2*n;i++)
        cin>>a[i];
    for(int i=1;i<=2*n;i++)
        cin>>b[i];
}

void solve()
{
    lf[1][0]=0;
    lf[1][1]=1;

    rt[1][0]=0;
    rt[1][1]=1;

    for(int i=2;i<=2*n;i++)
    {
        lf[i][0]=lf[i][1]=rt[i][0]=rt[i][1]=1e9;

        if(a[i-1]<=a[i])
        {
            lf[i][0]=lf[i-1][0];
            rt[i][0]=rt[i-1][0];
        }

        if(b[i-1]<=a[i])
        {
            lf[i][0]=min(lf[i][0],lf[i-1][1]);
            rt[i][0]=max(rt[i][0],rt[i-1][1]);
        }

        if(a[i-1]<=b[i])
        {
            lf[i][1]=lf[i-1][0]+1;
            rt[i][1]=rt[i-1][0]+1;
        }

        if(b[i-1]<=b[i])
        {
            lf[i][1]=min(lf[i][1],lf[i-1][1]+1);
            rt[i][1]=max(rt[i][1],rt[i-1][1]+1);
        }
    }

    if(lf[2*n][0]<=n&&n<=rt[2*n][0]||lf[2*n][1]<=n&&n<=rt[2*n][1])
    {
        vector<int> v;
        int j=n,l=1e9;
        for(int i=2*n;i>=1;i--)
        {
            if(lf[i][0]<=j&&j<=rt[i][0]&&a[i]<=l)
            {
                l=a[i];
                v.push_back(0);
            }
            else
            {
                l=b[i];
                v.push_back(1);
                j--;
            }
        }

        for(int i=v.size()-1;i>=0;i--)
            if(v[i]==0)cout<<"A";
            else cout<<"B";
            cout<<endl;
    }
    else cout<<-1<<endl;
}

int main()
{
    read();
    solve();
    return 0;
}

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