Submission #211579

#	Time	Username	Problem	Language	Result	Execution time	Memory
211579		Akashi	Building 4 (JOI20_building4)	C++14	100 / 100	622 ms	64000 KiB

building4

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

const int INF = 2e9;

struct usu{
    int mina, maxb, maxa, minb;
};
usu seg[1000005][2];

int n;
int a[1000005], b[1000005];
int val[1000005][2];

inline void solve(int n, int k, int nra, int nrb){
    if(k == 0) --nra;
    else --nrb;

    if(n > 1){
        for(int k2 = 0; k2 <= 1 ; ++k2){
            if(seg[n - 1][k2].mina != INF && seg[n - 1][k2].mina <= nra && seg[n - 1][k2].maxa >= nra && val[n - 1][k2] <= val[n][k]){
                solve(n - 1, k2, nra, nrb);
                break ;
            }
        }
    }

    if(k == 0) printf("A");
    else printf("B");
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d", &n);
    for(int i = 1; i <= 2 * n ; ++i){
        scanf("%d", &a[i]);
        val[i][0] = a[i];
    }
    for(int i = 1; i <= 2 * n ; ++i){
        scanf("%d", &b[i]);
        val[i][1] = b[i];
    }

    seg[1][0] = {1, 0, 1, 0};
    seg[1][1] = {0, 1, 0, 1};

    for(int i = 2; i <= 2 * n ; ++i){
        if(max(a[i], b[i]) < min(a[i - 1], b[i - 1])){
            printf("-1");
            return 0;
        }

        for(int k = 0; k < 2 ; ++k)
        seg[i][k] = {INF, -1, -1, INF};

        if(a[i] >= a[i - 1] && seg[i - 1][0].mina != INF){
            seg[i][0] = seg[i - 1][0];
            ++seg[i][0].mina;
            ++seg[i][0].maxa;
        }
        if(a[i] >= b[i - 1] && seg[i - 1][1].mina != INF){
            if(seg[i - 1][1].mina + 1 < seg[i][0].mina){
                seg[i][0].mina = seg[i - 1][1].mina + 1;
                seg[i][0].maxb = seg[i - 1][1].maxb;
            }
            if(seg[i - 1][1].maxa + 1 > seg[i][0].maxa){
                seg[i][0].maxa = seg[i - 1][1].maxa + 1;
                seg[i][0].minb = seg[i - 1][1].minb;
            }
        }

        if(b[i] >= a[i - 1] && seg[i - 1][0].mina != INF){
            seg[i][1] = seg[i - 1][0];
            ++seg[i][1].minb;
            ++seg[i][1].maxb;
        }
        if(b[i] >= b[i - 1] && seg[i - 1][1].mina != INF){
            if(seg[i - 1][1].maxb + 1 > seg[i][1].maxb){
                seg[i][1].mina = seg[i - 1][1].mina;
                seg[i][1].maxb = seg[i - 1][1].maxb + 1;
            }
            if(seg[i - 1][1].minb + 1 < seg[i][1].minb){
                seg[i][1].maxa = seg[i - 1][1].maxa;
                seg[i][1].minb = seg[i - 1][1].minb + 1;
            }
        }
    }


    for(int k = 0; k <= 1 ; ++k){
        if(seg[2 * n][k].mina <= n && seg[2 * n][k].maxa >= n){
            solve(2 * n, k, n, n);
            return 0;
        }
    }

    printf("-1");
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building4.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
building4.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~

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