Submission #870623

#	Time	Username	Problem	Language	Result	Execution time	Memory
870623		12345678	Building 4 (JOI20_building4)	C++17	100 / 100	202 ms	44728 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, a[2*nx], b[2*nx], dp[2][2*nx][2], c, x;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=2*n; i++) cin>>a[i];
    for (int i=1; i<=2*n; i++) cin>>b[i];
    dp[0][1][0]=dp[0][1][1]=1;
    for (int i=2; i<=2*n; i++)
    {
        dp[0][i][0]=dp[1][i][0]=1e9;
        dp[0][i][1]=dp[1][i][1]=-1e9;
        if (a[i]>=a[i-1]) dp[0][i][0]=min(dp[0][i][0], dp[0][i-1][0]+1), dp[0][i][1]=max(dp[0][i][1], dp[0][i-1][1]+1);
        if (a[i]>=b[i-1]) dp[0][i][0]=min(dp[0][i][0], dp[1][i-1][0]+1), dp[0][i][1]=max(dp[0][i][1], dp[1][i-1][1]+1);
        if (b[i]>=a[i-1]) dp[1][i][0]=min(dp[1][i][0], dp[0][i-1][0]), dp[1][i][1]=max(dp[1][i][1], dp[0][i-1][1]);
        if (b[i]>=b[i-1]) dp[1][i][0]=min(dp[1][i][0], dp[1][i-1][0]), dp[1][i][1]=max(dp[1][i][1], dp[1][i-1][1]);
        //cout<<i<<' '<<dp[0][i][0]<<' '<<dp[0][i][1]<<' '<<dp[1][i][0]<<' '<<dp[1][i][1]<<'\n';
    }
    vector<bool> ans;
    if (dp[0][2*n][0]<=n&&n<=dp[0][2*n][1]) x=n-1, c=0, ans.push_back(0);
    else if (dp[1][2*n][0]<=n&&n<=dp[1][2*n][1]) x=n, c=1, ans.push_back(1);
    else return cout<<-1, 0;
    for (int i=2*n-1; i>=1; i--)
    {
        if (dp[0][i][0]<=x&&x<=dp[0][i][1]&&a[i]<=(c?b[i+1]:a[i+1])) --x, c=0, ans.push_back(0);
        else ans.push_back(1), c=1;
    }
    for (int i=2*n-1; i>=0; i--) cout<<(ans[i]?'B':'A');
}

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