Submission #1291482

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

building4

#include<bits/stdc++.h>
using namespace std;
int n,a[500001],b[500001];
bitset<500005> dp[2];
bitset<500005> h[2][2001];
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()
{
    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(dp[0][n]||dp[1][n])
        {
            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;

        }
    else cout<<-1<<endl;
}

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

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