Submission #312176

#	Time	Username	Problem	Language	Result	Execution time	Memory
312176		vipghn2003	Building 4 (JOI20_building4)	C++14	100 / 100	367 ms	73976 KiB

building4

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;

const int N=1e6+5;
int n,a[N][2];
pii dp[N][2];
bool vis[N][2];

void calc(int i,int j)
{
    if(vis[i][j]) return ;
    vis[i][j]=true;
    dp[i][j].fi=1e9;
    dp[i][j].se=-1e9;
    if(a[i][j]<=a[i+1][0])
    {
        calc(i+1,0);
        dp[i][j].fi=min(dp[i][j].fi,dp[i+1][0].fi);
        dp[i][j].se=max(dp[i][j].se,dp[i+1][0].se);
    }
    if(a[i][j]<=a[i+1][1])
    {
        calc(i+1,1);
        dp[i][j].fi=min(dp[i][j].fi,dp[i+1][1].fi+1);
        dp[i][j].se=max(dp[i][j].se,dp[i+1][1].se+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    n*=2;
    for(int j=0;j<2;j++)
    {
        for(int i=1;i<=n;i++) cin>>a[i][j];
    }
    vis[n][0]=true;
    vis[n][1]=true;
    calc(0,0);
    if(dp[0][0].fi>n/2||dp[0][0].se<n/2) return cout<<-1,0;
    int need=n/2;
    int last=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i][0]>=a[i-1][last]&&dp[i][0].fi<=need&&dp[i][0].se>=need)
        {
            last=0;
            cout<<"A";
        }
        else
        {
            last=1;
            need--;
            cout<<"B";
        }
    }
}

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