Submission #1128312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128312		AndrijaM	Building 4 (JOI20_building4)	C++20	100 / 100	227 ms	49572 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

const int maxn=1000005;
const int mod=1e9+7;

int a[maxn];
int b[maxn];
pair<int,int> dp[maxn][2];

pair<int,int>add(pair<int,int>x)
{
    x.first++;
    x.second++;
    return x;
}
pair<int,int>u(pair<int,int>x,pair<int,int>y)
{
    if(x.first<0)return y;
    if(y.first<0)return x;
    return {min(x.first,y.first),max(x.second,y.second)};
}
bool in(pair<int,int>y,int x)
{
    return (y.first<=x && x<=y.second);
}

signed main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    n*=2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i][1]={-2e9,-2e9};
    }
    dp[1][1]={1,1};
    dp[1][0]={0,0};
    for(int i=1;i<n;i++)
    {
        if(a[i]<=a[i+1])
        {
            dp[i+1][1]=u(dp[i+1][1],add(dp[i][1]));
        }
        if(a[i]<=b[i+1])
        {
            dp[i+1][0]=u(dp[i+1][0],dp[i][1]);
        }
        if(b[i]<=a[i+1])
        {
            dp[i+1][1]=u(dp[i+1][1],add(dp[i][0]));
        }
        if(b[i]<=b[i+1])
        {
            dp[i+1][0]=u(dp[i+1][0],dp[i][0]);
        }
    }
    int x=n/2;
    if(in(dp[n][0],x)==0 && in(dp[n][1],x)==0)
    {
        cout<<-1<<endl;
        return 0;
    }
    string ans;
    int prev=2e9;
    for(int i=n;i>=1;i--)
    {
        if(in(dp[i][0],x)==1 && prev>=b[i])
        {
            ans+='B';
            prev=b[i];
        }
        else
        {
            ans+='A';
            x--;
            prev=a[i];
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    return 0;
}

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