제출 #1152505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152505		mingga	Building 4 (JOI20_building4)	C++20	100 / 100	167 ms	49516 KiB

building4

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 1e6 + 7;
int n, a[N][2];
int mn[N][2], mx[N][2];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    #define task ""
    if(fopen(task ".INP", "r")) {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= 2 * n; i++) cin >> a[i][0];
    for(int i = 1; i <= 2 * n; i++) cin >> a[i][1];
    for(int i = 1; i <= 2 * n; i++) {
        mx[i][0] = mx[i][1] = -inf;
        mn[i][0] = mn[i][1] = inf;
    }
    for(int i = 1; i <= 2 * n; i++) {
        if(a[i][0] >= a[i - 1][0]) {
            mx[i][0] = max(mx[i - 1][0], mx[i][0]);
            mn[i][0] = min(mn[i - 1][0], mn[i][0]);
        }
        if(a[i][1] >= a[i - 1][0]) {
            mx[i][1] = max(mx[i][1], mx[i - 1][0] + 1);
            mn[i][1] = min(mn[i][1], mn[i - 1][0] + 1);
        }
        if(a[i][0] >= a[i - 1][1]) {
            mx[i][0] = max(mx[i - 1][1], mx[i][0]);
            mn[i][0] = min(mn[i - 1][1], mn[i][0]);
        }
        if(a[i][1] >= a[i - 1][1]) {
            mx[i][1] = max(mx[i][1], mx[i - 1][1] + 1);
            mn[i][1] = min(mn[i][1], mn[i - 1][1] + 1);
        }
        // cout << i << ' ' << mn[i][0] << ' ' << mx[i][0] << ' ' << mn[i][1] << ' ' << mx[i][1] << ln;
    }
    int cur_i = 2 * n, cur_j;
    vector<char> ans;
    if(mx[n * 2][0] >= n and mn[n * 2][0] <= n) {
        cur_j = 0;
    } else if(mx[n * 2][1] >= n and mn[n * 2][1] <= n) {
        cur_j = 1;
    } else {
        cout << -1;
        return 0;
    }
    int m = n;
    while(sz(ans) < 2 * n) {
        if(cur_j == 0) ans.pb('A');
        else ans.pb('B');
        cur_i--;
        m -= cur_j;
        if(mx[cur_i][cur_j] < m or mn[cur_i][cur_j] > m or (cur_i > 1 and a[cur_i + 1][cur_j] < a[cur_i][cur_j])) {
            cur_j ^= 1;
        }
    }
    reverse(all(ans));
    for(auto x : ans) cout << x;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

컴파일 시 표준 에러 (stderr) 메시지

building4.cpp: In function 'int main()':
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(task ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
building4.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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