Submission #563861

#	Time	Username	Problem	Language	Result	Execution time	Memory
563861		groshi	Building 4 (JOI20_building4)	C++17	11 / 100	13 ms	19540 KiB

building4

#include<iostream>

using namespace std;
int inf=1e9;
pair<int,int> dp[600000][2];
char wyn[600000];
int a[600000],b[600000];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<=2*n;i++)
    {
        dp[i][0]={inf,-inf};
        dp[i][1]={inf,-inf};
    }
    for(int i=0;i<2*n;i++)
        cin>>a[i];
    for(int i=0;i<2*n;i++)
        cin>>b[i];
    dp[0][0]={0,0};
    dp[0][1]={1,1};
    for(int i=0;i<2*n;i++)
    {
        if(a[i]<=a[i+1])
        {
            dp[i+1][1].first=min(dp[i][1].first+1,dp[i+1][1].first);
            dp[i+1][1].second=max(dp[i][1].second+1,dp[i+1][1].second);
        }
        if(a[i]<=b[i+1])
        {
            dp[i+1][0].first=min(dp[i][1].first,dp[i+1][0].first);
            dp[i+1][0].second=max(dp[i+1][0].second,dp[i][1].second);
        }
        if(b[i]<=a[i+1])
        {
            dp[i+1][1].first=min(dp[i+1][1].first,dp[i][0].first+1);
            dp[i+1][1].second=max(dp[i+1][1].second,dp[i][0].second+1);
        }
        if(b[i]<=b[i+1])
        {
            dp[i+1][0].first=min(dp[i+1][0].first,dp[i][0].first);
            dp[i+1][0].second=max(dp[i+1][0].second,dp[i][0].second);
        }
    }
    int zostalo=n,ost=inf;
    for(int i=2*n-1;i>=0;i--)
    {
        if(dp[i][1].first<=zostalo && dp[i][1].second>=zostalo && a[i]<=ost)
        {
            wyn[i]='A';
            ost=a[i];
            zostalo--;
        }
        else if(dp[i][0].first<=zostalo && dp[i][0].second>=zostalo && b[i]<=ost)
        {
            wyn[i]='B';
            ost=b[i];
        }
        else{
            cout<<"-1";
            return 0;
        }
    }
    for(int i=0;i<2*n;i++)
        cout<<wyn[i];
    return 0;
}

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