Submission #226768

#	Time	Username	Problem	Language	Result	Execution time	Memory
226768		MKopchev	Building 4 (JOI20_building4)	C++14	100 / 100	471 ms	45544 KiB

building4

#include<bits/stdc++.h>
using namespace std;
const int nmax=5e5+42;

int n;
int a[2*nmax],b[2*nmax];

string current;

pair<int,int> dp[2*nmax][2];

pair<int,int> my_merge(pair<int,int> u,pair<int,int> v)
{
    //cout<<"my_merge "<<u.first<<" "<<u.second<<" "<<v.first<<" "<<v.second<<endl;

    if(u.first>u.second)return v;
    if(v.first>v.second)return u;

    return {min(u.first,v.first),max(u.second,v.second)};
}

bool inside(pair<int,int> cur,int val)
{
    return cur.first<=val&&val<=cur.second;
}
int main()
{
    scanf("%i",&n);

    for(int i=1;i<=2*n;i++)scanf("%i",&a[i]);
    for(int i=1;i<=2*n;i++)scanf("%i",&b[i]);

    for(int pos=0;pos<=2*n;pos++)
        for(int side=0;side<2;side++)
            dp[pos][side]={1,0};

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

    for(int pos=1;pos<=2*n;pos++)
        for(int side=0;side<2;side++)
        {
            if(side==0)
            {
                if(a[pos-1]<=a[pos])dp[pos][side]=my_merge(dp[pos][side],dp[pos-1][0]);
                if(b[pos-1]<=a[pos])dp[pos][side]=my_merge(dp[pos][side],dp[pos-1][1]);

                if(dp[pos][side].first<=dp[pos][side].second)dp[pos][side].first++,dp[pos][side].second++;
            }
            else
            {
                if(a[pos-1]<=b[pos])dp[pos][side]=my_merge(dp[pos][side],dp[pos-1][0]);
                if(b[pos-1]<=b[pos])dp[pos][side]=my_merge(dp[pos][side],dp[pos-1][1]);
            }

            dp[pos][side].second=min(dp[pos][side].second,n);

            dp[pos][side].first=max(dp[pos][side].first,pos-n);

            //cout<<pos<<" "<<side<<" -> "<<dp[pos][side].first<<" "<<dp[pos][side].second<<endl;
        }

    int pos=2*n,a_now=n,side=0;

    if(dp[2*n][0].first<=dp[2*n][0].second);
    else if(dp[2*n][1].first<=dp[2*n][1].second)side=1;
    else {printf("-1\n");return 0;}

    while(pos)
    {
        current.push_back('A'+side);

        if(side==0)
        {
            a_now--;

            if(a[pos-1]<=a[pos]&&inside(dp[pos-1][0],a_now))side=0;
            else side=1;
        }
        else
        {
            if(a[pos-1]<=b[pos]&&inside(dp[pos-1][0],a_now))side=0;
            else side=1;
        }
        pos--;
    }

    reverse(current.begin(),current.end());

    for(int i=0;i<2*n;i++)
        printf("%c",current[i]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
building4.cpp:30:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=2*n;i++)scanf("%i",&a[i]);
                            ~~~~~^~~~~~~~~~~~
building4.cpp:31:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=2*n;i++)scanf("%i",&b[i]);
                            ~~~~~^~~~~~~~~~~~

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