Submission #1277663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277663		wedonttalkanymore	Building 4 (JOI20_building4)	C++20	100 / 100	190 ms	49508 KiB

building4

#include <bits/stdc++.h>
/*
    Brute to win
*/
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 = 1e6 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int n;
int a[N], b[N];
int dpmin[N][2], dpmax[N][2]; // 1 la co chon B o thoi diem hien tai hay khong
vector <char> path;

void trace(int id) {
    int need = n;
    int pos = 2 * n, type = id;
//    cout << need << ' ' << pos << ' ' << type << '\n';
    while(pos > 0) {
//    	cout << need << ' ' << pos << ' ' << type << '\n';
//    	return;
//    	if (pos < 1) break;
        if (dpmin[pos][type] <= need && dpmax[pos][type] >= need) {
            if (type == 1) {
            	path.push_back('B');
            	need--;
            	need = max(0LL, need);
			}
            else path.push_back('A');
//            if (need == 0) return;
        }
        if (type == 0) {
            if (dpmin[pos - 1][0] <= need && dpmax[pos - 1][0] >= need && a[pos - 1] <= a[pos]) {
                pos--;
                type = 0;
            }
            else if (dpmin[pos - 1][1] <= need && dpmax[pos - 1][1] >= need && b[pos - 1] <= a[pos]) {
                pos--;
                type = 1;
            }
        }
        else {
//        	cout << "gay" << '\n';
//			cout << pos - 1 << ' ' << dpmin[pos - 1][1] << ' ' << dpmax[pos - 1][1] << ' ' << need << '\n';
            if (dpmin[pos - 1][0] <= need && dpmax[pos - 1][0] >= need && a[pos - 1] <= b[pos]) {
                pos--;
                type = 0;
            }
            else if (dpmin[pos - 1][1] <= need && dpmax[pos - 1][1] >= need && b[pos - 1] <= b[pos]) {
                pos--;
                type = 1;
            }
//            return;
        }
    }
}

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];
    for (int i = 1; i <= 2 * n; i++) dpmin[i][0] = dpmin[i][1] = inf;
    dpmin[1][0] = 0, dpmin[1][1] = 1;
    for (int i = 2; i <= 2 * n; i++) {
        if (a[i - 1] <= a[i]) dpmin[i][0] = min(dpmin[i][0], dpmin[i - 1][0]);
        if (b[i - 1] <= a[i]) dpmin[i][0] = min(dpmin[i][0], dpmin[i - 1][1]);
        if (a[i - 1] <= b[i]) dpmin[i][1] = min(dpmin[i][1], dpmin[i - 1][0] + 1);
        if (b[i - 1] <= b[i]) dpmin[i][1] = min(dpmin[i][1], dpmin[i - 1][1] + 1);
    }
    dpmax[1][0] = 0, dpmax[1][1] = 1;
    for (int i = 2; i <= 2 * n; i++) {
//    	cout << i << ' ';
        // dpmax[i][0] = 0, dpmax[i][1] = 1;
        // if (i == 2) cout << b[i - 1] << ' ' << b[i] << '\n';
        if (a[i - 1] <= a[i]) dpmax[i][0] = max(dpmax[i][0], dpmax[i - 1][0]);
        if (b[i - 1] <= a[i]) dpmax[i][0] = max(dpmax[i][0], dpmax[i - 1][1]);
        if (a[i - 1] <= b[i]) dpmax[i][1] = max(dpmax[i][1], dpmax[i - 1][0] + 1);
        if (b[i - 1] <= b[i]) dpmax[i][1] = max(dpmax[i][1], dpmax[i - 1][1] + 1);
    }
//    for (int i = 1; i <= 2 * n; i++) {
//        cout << dpmin[i][1] << ' ' << dpmax[i][1] << '\n';
//    }
    if (dpmin[2 * n][0] <= n && dpmax[2 * n][0] >= n) {
        trace(0);
        reverse(path.begin(), path.end());
        for (auto x : path) cout << x;
    }
    else if (dpmin[2 * n][1] <= n && dpmax[2 * n][1] >= n) {
        trace(1);
        reverse(path.begin(), path.end());
        for (auto x : path) cout << x;
    }
    else cout << -1;
    return 0;
}

Compilation message (stderr)

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

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