제출 #705935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705935		pakhomovee	건물 4 (JOI20_building4)	C++17	100 / 100	321 ms	75864 KiB

building4

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <stdlib.h>
#include <map>
#include <random>
#include <cstring>
#include <functional>
#include <iomanip>
#include <cassert>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <array>

using namespace std;
#define int long long
const int inf = 1e9;
void solve() {
    int n;
    cin >> n;
    n *= 2;
    vector<int> a(n);
    vector<int> b(n);
    for (int& i : a) cin >> i;
    for (int& i : b) cin >> i;
    pair<int, int> dp[n][2];
    for (int i = 0; i < n; ++i) {
        dp[i][0] = dp[i][1] = { inf, -inf };
    }
    dp[0][0] = { 1, 1 };
    dp[0][1] = { 0, 0 };
    auto f = [&] (pair<int, int> x, pair<int, int> y, int offset) { return make_pair(min(x.first, y.first + offset), max(x.second, y.second + offset)); };
    for (int i = 0; i + 1 < n; ++i) {
        if (a[i + 1] >= a[i]) dp[i + 1][0] = f(dp[i + 1][0], dp[i][0], 1);
        if (a[i + 1] >= b[i]) dp[i + 1][0] = f(dp[i + 1][0], dp[i][1], 1);
        if (b[i + 1] >= a[i]) dp[i + 1][1] = f(dp[i + 1][1], dp[i][0], 0);
        if (b[i + 1] >= b[i]) dp[i + 1][1] = f(dp[i + 1][1], dp[i][1], 0);
    }
    vector<int> res;
    int ptr = n - 1;
    int can = n / 2;
    int pr = inf;
    while (ptr >= 0) {
        if (dp[ptr][0].first <= can && can <= dp[ptr][0].second && a[ptr] <= pr) {
            res.push_back(0);
            pr = a[ptr];
            --can;
        } else if (dp[ptr][1].first <= can && can <= dp[ptr][1].second && b[ptr] <= pr) {
            res.push_back(1);
            pr = b[ptr];
        } else {
            cout << -1;
            return;
        }
        --ptr;
    }
    reverse(res.begin(), res.end());
    const vector<char> lets = { 'A', 'B' };
    for (int i : res) {
        cout << lets[i];
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--) {
        solve();
    }
}
/*
3
2 5 4 9 15 11
6 7 6 8 12 14
 */

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