Submission #1291501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291501		simona1230	건물 4 (JOI20_building4)	C++20	11 / 100	887 ms	513664 KiB

building4

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

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]=1e9;
        rt[i][0]=rt[i][1]=0;

        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);
        }
    }

    dp[0][1]=dp[1][0]=1;
    h[0][1]=dp[0];
    h[1][1]=dp[1];
    for(int i=2;i<=2*n;i++)
    {
        bitset<500005> dp0,dp1;
        if(a[i-1]<=a[i]&&b[i-1]>a[i])
        {
            dp0=(dp[0]<<1);
        }
        else if(a[i-1]>a[i]&&b[i-1]<=a[i])
        {
            dp0=(dp[1]<<1);
        }
        else if(a[i-1]<=a[i]&&b[i-1]<=a[i])
        {
            dp0=(dp[0]<<1)|(dp[1]<<1);
        }
        else dp0=0;

        if(a[i-1]<=b[i]&&b[i-1]>b[i])
        {
            dp1=(dp[0]);
        }
        else if(a[i-1]>b[i]&&b[i-1]<=b[i])
        {
            dp1=(dp[1]);
        }
        else if(a[i-1]<=b[i]&&b[i-1]<=b[i])
        {
            dp1=(dp[0])|(dp[1]);
        }
        else dp1=0;

        dp[0]=dp0;
        dp[1]=dp1;
        h[0][i]=dp[0];
        h[1][i]=dp[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--)
            {
                //cout<<l<<" !"<<endl;
                if(h[0][i][j]&&l>=a[i])
                {
                    j--;
                    l=a[i];
                    v.push_back(0);
                }
                else l=b[i],v.push_back(1);
            }

            for(int i=v.size()-1;i>=0;i--)
                if(v[i]==0)cout<<"A";
                else cout<<"B";
                cout<<endl;
        /*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: 11 / 11
• Subtask 2: 0 / 89