Submission #261612

#	Time	Username	Problem	Language	Result	Execution time	Memory
261612		KCSC	Building 4 (JOI20_building4)	C++14	100 / 100	1276 ms	45340 KiB

building4

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int DIM = 1000005;

pair<int, int> seg[2][DIM];
char ans[DIM];
int arr[2][DIM];

void solve(int k, int n, int rem) {
    if (n == 0)
        cout << (ans + 1);
    else {
        if (k == 0)
            ans[n] = 'A';
        else
            ans[n] = 'B';
        if (arr[0][n - 1] <= arr[k][n] and seg[0][n - 1].first != -1 and
            seg[0][n - 1].first <= rem - (1 - k) and rem - (1 - k) <= seg[0][n - 1].second)
            solve(0, n - 1, rem - (1 - k));
        else
            solve(1, n - 1, rem - (1 - k));
    }
}

void update(pair<int, int> &s1, pair<int, int> &s2) {
    if (s2.first == -1)
        return;
    if (s1.first == -1)
        s1 = s2;
    else
        s1 = make_pair(min(s1.first, s2.first), max(s1.second, s2.second));
}

int main(void) {
  //  freopen("building4.in", "r", stdin);
  //  freopen("building4.out", "w", stdout);
    int n;
    cin >> n;
    for (int k = 0; k <= 1; ++k) {
        for (int i = 1; i <= n * 2; ++i) {
            cin >> arr[k][i];
            seg[k][i] = {-1, -1};
        }
    }
    seg[0][0] = {0, 0};
    for (int i = 1; i <= n * 2; ++i) {
        for (int k1 = 0; k1 <= 1; ++k1)
        for (int k2 = 0; k2 <= 1; ++k2)
            if (arr[k1][i - 1] <= arr[k2][i])
                update(seg[k2][i], seg[k1][i - 1]);
        if (seg[0][i].first != -1)
            ++seg[0][i].first, ++seg[0][i].second;
    }
  /*  for (int i = 0; i <= n * 2; ++i) {
        for (int k = 0; k <= 1; ++k)
            cout << seg[k][i].first << " " << seg[k][i].second << "    ";
        cout << endl;
    } */
    if (seg[0][n * 2].first != -1 and seg[0][n * 2].first <= n and seg[0][n * 2].second >= n)
        solve(0, n * 2, n);
    else if (seg[1][n * 2].first != -1 and seg[1][n * 2].first <= n and seg[1][n * 2].second >= n)
        solve(1, n * 2, n);
    else
        cout << -1 << "\n";
    return 0;
}

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