Submission #976578

#	Time	Username	Problem	Language	Result	Execution time	Memory
976578		LinkedArray	Building 4 (JOI20_building4)	C++17	100 / 100	180 ms	57160 KiB

building4

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

using ll = long long;
#define pb push_back

const int MAX_N = 1e6;
const int INF = 1e9;

int val[2][2 * MAX_N + 5];
int st_min[2][2 * MAX_N + 5], dr_max[2][2 * MAX_N + 5];
/* 0 -> a[ ]; 1 -> b[ ] */

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, i, j, k, prev_val, num_a, num_b;
    string ans;

    cin >> n;
    for (i = 1; i <= 2 * n; i++) {
        cin >> val[0][i];
    }
    for (i = 1; i <= 2 * n; i++) {
        cin >> val[1][i];
    }
    for (i = 1; i <= 2 * n; i++) {
        /* iau variante */
        for (j = 0; j < 2; j++) {
            st_min[j][i] = INF;
            dr_max[j][i] = -INF;
        }
        for (j = 0; j < 2; j++) {
            if (val[j][i - 1] <= val[0][i]) {
                st_min[0][i] = min(st_min[0][i], st_min[j][i - 1] + 1);
                dr_max[0][i] = max(dr_max[0][i], dr_max[j][i - 1] + 1);
            }
            if (val[j][i - 1] <= val[1][i]) {
                st_min[1][i] = min(st_min[1][i], st_min[j][i - 1]);
                dr_max[1][i] = max(dr_max[1][i], dr_max[j][i - 1]);
            }
        }
    }

    /* go from largest to smallest */
    prev_val = INF;
    num_a = 0;
    for (i = 2 * n; i >= 1; i--) {
        num_b = n - num_a;
        if (prev_val >= val[0][i] && st_min[0][i] <= num_b && num_b <= dr_max[0][i]) {
            ans.push_back('A');
            num_a++;

            prev_val = val[0][i];
        } else if (prev_val >= val[1][i] && st_min[1][i] <= num_b && num_b <= dr_max[1][i]) {
            ans.push_back('B');

            prev_val = val[1][i];
        } else {
            cout << "-1\n";
            return 0;
        }
    }

    /* take from smallest to largest */
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:18:18: warning: unused variable 'k' [-Wunused-variable]
   18 |     int n, i, j, k, prev_val, num_a, num_b;
      |                  ^

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