Submission #937763

#	Time	Username	Problem	Language	Result	Execution time	Memory
937763		borisAngelov	Building 4 (JOI20_building4)	C++17	100 / 100	215 ms	45464 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000005;

int n;

int a[maxn];
int b[maxn];

pair<int, int> dpA[maxn];
pair<int, int> dpB[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= 2 * n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= 2 * n; ++i)
    {
        cin >> b[i];
    }

    dpA[1] = make_pair(1, 1);
    dpB[1] = make_pair(0, 0);

    for (int pos = 2; pos <= 2 * n; ++pos)
    {
        dpA[pos] = make_pair(-1, -1);
        dpB[pos] = make_pair(-1, -1);

        if (a[pos] >= a[pos - 1])
        {
            if (dpA[pos - 1] != make_pair(-1, -1))
            {
                dpA[pos].first = dpA[pos - 1].first + 1;
                dpA[pos].second = dpA[pos - 1].second + 1;
            }
        }

        if (a[pos] >= b[pos - 1] && dpB[pos - 1] != make_pair(-1, -1))
        {
            if (dpA[pos] == make_pair(-1, -1))
            {
                dpA[pos].first = dpB[pos - 1].first + 1;
                dpA[pos].second = dpB[pos - 1].second + 1;
            }
            else
            {
                dpA[pos].first = min(dpA[pos].first, dpB[pos - 1].first + 1);
                dpA[pos].second = max(dpA[pos].second, dpB[pos - 1].second + 1);
            }
        }

        if (b[pos] >= a[pos - 1])
        {
            if (dpA[pos - 1] != make_pair(-1, -1))
            {
                dpB[pos] = dpA[pos - 1];
            }
        }

        if (b[pos] >= b[pos - 1] && dpB[pos - 1] != make_pair(-1, -1))
        {
            if (dpB[pos] == make_pair(-1, -1))
            {
                dpB[pos] = dpB[pos - 1];
            }
            else
            {
                dpB[pos].first = min(dpB[pos].first, dpB[pos - 1].first);
                dpB[pos].second = max(dpB[pos].second, dpB[pos - 1].second);
            }
        }
    }

    int curr = -1;

    //cout << dpA[2 * n].first << " " << dpA[2 * n].second << endl;
    //cout << dpB[2 * n].first << " " << dpB[2 * n].second << endl;

    if (dpA[2 * n].first <= n && n <= dpA[2 * n].second)
    {
        curr = 0;
    }

    if (dpB[2 * n].first <= n && n <= dpB[2 * n].second)
    {
        curr = 1;
    }

    if (curr == -1)
    {
        //cout << "here" << endl;
        cout << -1 << endl;
        return 0;
    }

    stack<char> result;
    result.push(char(curr + 'A'));

    int bound = (curr == 0 ? n - 1 : n);

    for (int pos = 2 * n - 1; pos >= 1; --pos)
    {
        int prv = (curr == 0 ? a[pos + 1] : b[pos + 1]);
        curr = -1;

        if (bound > 0 && prv >= a[pos] && dpA[pos].first <= bound && bound <= dpA[pos].second)
        {
            curr = 0;
            --bound;
        }
        else if (prv >= b[pos] && dpB[pos].first <= bound && bound <= dpB[pos].second)
        {
            curr = 1;
        }

        if (curr == -1)
        {
            cout << -1 << endl;
            return 0;
        }

        result.push(char(curr + 'A'));
    }

    while (!result.empty())
    {
        cout << result.top();
        result.pop();
    }

    cout << endl;

    return 0;
}

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