제출 #1285353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285353		Faisal_Saqib	건물 4 (JOI20_building4)	C++20	100 / 100	171 ms	25956 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+1;
int a[N][2];
#define range pair<int,int>
#define mx second
#define mi first
range dp[N][2];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<2;i++)
    {
        for(int j=1;j<=2*n;j++)
        {
            cin>>a[j][i];
            dp[j][i]={1e9,-1e9}; // null range;
        }
    }
    dp[1][0]={1,1}; // cnt A
    dp[1][1]={0,0};
    for(int i=2;i<=2*n;i++)
    {
        for(int k=0;k<2;k++)
        {
            for(int j=0;j<2;j++)
            {
                if(a[i][k]>=a[i-1][j])
                {
                    // k=0 we add one to cnt
                    // k=1 we dont add one to cnt
                    dp[i][k]={min(dp[i][k].mi,dp[i-1][j].mi+1-k),max(dp[i][k].mx,dp[i-1][j].mx+1-k)};
                }
            }
        }
    }
    int p=-1;
    if(dp[2*n][0].mi<=n and n<=dp[2*n][0].mx)
    {
        p=0;
    }
    else if(dp[2*n][1].mi<=n and n<=dp[2*n][1].mx)
    {
        p=1;
    }
    else
    {
        cout<<-1<<endl;
        return 0;
    }
    string ans;
    int cn=n-(1-p);
    ans+=(p?'B':'A');
    for(int j=2*n-1;j>=1;j--)
    {
        for(int i=0;i<2;i++)
        {
            if(dp[j][i].mi<=cn and cn<=dp[j][i].mx and a[j+1][p]>=a[j][i])
            {
                cn-=(1-i);
                ans+=(i?'B':'A');
                p=i;
                break;
            }
        }
    }
    reverse(begin(ans),end(ans));
    cout<<ans<<endl;
}

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