Submission #728181

#	Time	Username	Problem	Language	Result	Execution time	Memory
728181		nguyentunglam	Building 4 (JOI20_building4)	C++17	100 / 100	249 ms	48336 KiB

building4

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e6 + 10;
int a[2][N], g[2][N], f[2][N], ans[N];
int cur, n;

void trace(int type, int i) {
    ans[i] = type;
    cur += type;
    if (i == 1) return;
    if (a[type][i] >= a[0][i - 1] && cur + g[0][i - 1] <= n && n <= cur + f[0][i - 1]) trace(0, i - 1);
    else trace(1, i - 1);
}

int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n * 2; i++) cin >> a[0][i];

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

    for(int i = 1; i <= n * 2; i++) {
        g[0][i] = g[1][i] = 1e9;
        for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) if (a[j][i] >= a[k][i - 1]) {
            f[j][i] = max(f[j][i], f[k][i - 1] + j);
            g[j][i] = min(g[j][i], g[k][i - 1] + j);
        }
    }
    if (g[0][2 * n] <= n && n <= f[0][2 * n]) trace(0, 2 * n);
    else if (g[1][2 * n] <= n && n <= f[1][2 * n]) trace(1, 2 * n);
    else return cout << -1, 0;
    for(int i = 1; i <= 2 * n; i++) cout << (ans[i] == 1 ? "B" : "A");
}

Compilation message (stderr)

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

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