제출 #678399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678399		MarcuMihai	건물 4 (JOI20_building4)	C++14	100 / 100	923 ms	75580 KiB

building4

#include <iostream>

using namespace std;

int n;
struct el
{
    int sus;
    int jos;
};
el a[1000005];

struct din
{
    int minim;
    int maxim;
};
din dp[1000005][2];

void inapoi(int n, int niv, int puse)
{

    if(n==0)
        return;

    int x;
    if(niv==0)
        x=a[n].sus;
    else
        x=a[n].jos;

    if(dp[n-1][0].minim<=puse && dp[n-1][0].maxim>=puse && x>=a[n-1].sus)
        inapoi(n-1, 0, puse-1);
    else
        inapoi(n-1, 1, puse);


    if(niv==0)
        cout<<'A';
    else
        cout<<'B';
}


int main()
{
    cin>>n;
    for(int i=1; i<=2*n; ++i)
        cin>>a[i].sus;
    for(int i=1; i<=2*n; ++i)
        cin>>a[i].jos;

    for(int i=1; i<=2*n; ++i)
    {
        dp[i][0].minim=dp[i][1].minim=999999999;
        dp[i][0].maxim=dp[i][1].maxim=-999999999;
    }

    dp[1][0]= {1,1};
    dp[1][1]= {0,0};

    for(int i=2; i<=2*n; ++i)
    {
        if(a[i].sus>=a[i-1].sus)
        {
            dp[i][0].minim=min(dp[i][0].minim, dp[i-1][0].minim+1);
            dp[i][0].maxim=max(dp[i][0].maxim, dp[i-1][0].maxim+1);
        }
        if(a[i].sus>=a[i-1].jos)
        {
            dp[i][0].minim=min(dp[i][0].minim, dp[i-1][1].minim+1);
            dp[i][0].maxim=max(dp[i][0].maxim, dp[i-1][1].maxim+1);
        }



        if(a[i].jos>=a[i-1].sus)
        {
            dp[i][1].minim=min(dp[i][1].minim, dp[i-1][0].minim);
            dp[i][1].maxim=max(dp[i][1].maxim, dp[i-1][0].maxim);
        }
        if(a[i].jos>=a[i-1].jos)
        {
            dp[i][1].minim=min(dp[i][1].minim, dp[i-1][1].minim);
            dp[i][1].maxim=max(dp[i][1].maxim, dp[i-1][1].maxim);
        }
    }
    if((dp[2*n][0].minim>n || dp[2*n][0].maxim<n) && (dp[2*n][1].minim>n || dp[2*n][1].maxim<n))
        cout<<-1;


    else
    {


        if(dp[2*n][0].minim<=n && dp[2*n][0].maxim>=n)
        {
            inapoi(2*n,0,n-1);
        }
        else
        {
            inapoi(2*n,1,n);
        }

    }


    return 0;
}

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