Submission #1254938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254938		wedonttalkanymore	건물 4 (JOI20_building4)	C++20	0 / 100	23 ms	328 KiB

building4

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

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 1e5 + 5;

int n, a[2 * N], b[2 * N];
bool f[2][N][3];
char tr[2][N][3];
char res[2 * N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

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

    a[0] = b[0] = -1e18;
    f[0][0][0] = 1;

    for (int i = 1; i <= 2 * n; i++) {
        int cur = i & 1, pre = cur ^ 1;
        for (int k = 0; k <= min(i, n); k++) {
            for (int t = 0; t < 3; t++) f[cur][k][t] = 0;
        }

        for (int k = 0; k <= min(i, n); k++) {
            int j = i - k;
            if (k > 0) {
                for (int t = 0; t < 3; t++) {
                    if (!f[pre][k - 1][t]) continue;
                    int val = (t == 1 ? a[i - 1] : (t == 2 ? b[i - 1] : -1e18));
                    if (a[i] >= val) {
                        f[cur][k][1] = 1;
                        tr[cur][k][1] = t;
                    }
                }
            }
            if (j > 0) {
                for (int t = 0; t < 3; t++) {
                    if (!f[pre][k][t]) continue;
                    int val = (t == 1 ? a[i - 1] : (t == 2 ? b[i - 1] : -1e18));
                    if (b[i] >= val) {
                        f[cur][k][2] = 1;
                        tr[cur][k][2] = t;
                    }
                }
            }
        }
    }

    int last = -1;
    if (f[2 * n % 2][n][1]) last = 1;
    else if (f[2 * n % 2][n][2]) last = 2;

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

    int i = 2 * n, k = n;
    while (i) {
        int cur = i & 1;
        if (last == 1) {
            res[i - 1] = 'A';
            last = tr[cur][k][1];
            k--;
        } else {
            res[i - 1] = 'B';
            last = tr[cur][k][2];
        }
        i--;
    }

    for (int i = 0; i < 2 * n; i++) cout << res[i];
    cout << '\n';
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
building4.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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