Submission #522165

#	Time	Username	Problem	Language	Result	Execution time	Memory
522165		Rainbowbunny	Building 4 (JOI20_building4)	C++17	100 / 100	261 ms	48276 KiB

building4

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
const int INF = 1e9;

int n;
int A[MAXN][2], l[MAXN][2], r[MAXN][2];
int ans[MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= 2 * n; i++)
    {
        cin >> A[i][0];
    }
    for(int i = 1; i <= 2 * n; i++)
    {
        cin >> A[i][1];
    }

    for(int i = 1; i <= 2 * n; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            l[i][j] = INF; r[i][j] = -INF;
            for(int k = 0; k < 2; k++)
            {
                if(A[i][j] >= A[i - 1][k])
                {
                    l[i][j] = min(l[i][j], l[i - 1][k] + j);
                    r[i][j] = max(r[i][j], r[i - 1][k] + j);
                }
            }
        }
    }

    int root = -1, cntb = n;
    for(int i = 0; i < 2; i++)
    {
        if(l[2 * n][i] <= cntb and r[2 * n][i] >= cntb)
        {
            root = i;
        }
    }

    if(root == -1)
    {
        cout << -1 << '\n';
    }
    else
    {
        for(int i = 2 * n; i >= 1; i--)
        {
            for(int j = 0; j < 2; j++)
            {
                if(A[i][root] >= A[i - 1][j] and cntb - root >= l[i - 1][j] and cntb - root <= r[i - 1][j])
                {
                    ans[i] = root;
                    cntb -= root;
                    root = j;
                    break;
                }
            }
        }
        for(int i = 1; i <= 2 * n; i++)
        {
            cout << char(ans[i] + 'A');
        }
        cout << '\n';
    }
}

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