제출 #710744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710744		lukameladze	건물 4 (JOI20_building4)	C++14	100 / 100	377 ms	48168 KiB

building4

# include <bits/stdc++.h>
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
using namespace std;
const int N = 1e6 + 5,inf = 1e9;
int le[2][N],ri[2][N], a[2][N],n,id,lst,cnt,ans[N];
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 1; i <= 2*n; i++) {
        cin>>a[0][i];
        le[0][i] = inf; le[1][i] = inf;
        ri[0][i] = 0; ri[1][i] = 0;
    }
    for (int i = 1; i <= 2*n; i++) {
        cin>>a[1][i];
    }
    for (int i = 1; i <= 2*n; i++) {
        for (int j = 0; j <= 1; j++) {
            if (j == 0) {
               if (a[0][i - 1] <= a[0][i]) {
                   le[0][i] = min(le[0][i - 1] + 1, le[0][i]);
                   ri[0][i] = max(ri[0][i - 1] + 1, ri[0][i]);
               }
               if (a[1][i - 1] <= a[0][i]) {
                   le[0][i] = min(le[1][i - 1] + 1, le[0][i]);
                   ri[0][i] = max(ri[1][i - 1] + 1, ri[0][i]);
               }
                continue;
            }
            if (a[0][i - 1] <= a[1][i]) {
                le[1][i] = min(le[0][i - 1], le[1][i]);
                ri[1][i] = max(ri[0][i - 1], ri[1][i]);
            }
            if (a[1][i - 1] <= a[1][i]) {
                le[1][i] = min(le[1][i - 1], le[1][i]);
                ri[1][i] = max(ri[1][i - 1], ri[1][i]);
            }
        }
    }
    id = -1;
    if (n >= le[0][2 * n] && n <= ri[0][2 * n])  id = 0;
    else  {
        if (n >= le[1][2 * n] && n <= ri[1][2 * n])  id = 1;
    }
    if (id == -1)  {
        cout<<-1<<"\n";
        exit(0);
    }
    cnt = 0;
    lst = 2 * n;
    while (lst >= 1) {
        if (id == 0) cnt++,ans[lst] = 1;
        else ans[lst] = 2;
        if (lst == 1) break;
        if (le[0][lst - 1] + cnt <= n && ri[0][lst - 1] + cnt >= n && a[0][lst - 1] <= a[id][lst]) {
            id = 0;
            lst--;
            continue;
        }
        id = 1;
        lst--;
    }
    for (int i = 1; i <= 2 * n; i++) {
        cout<<(ans[i] == 1 ? "A" : "B");
    }
}

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

building4.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main() {
      | ^~~~

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