Submission #374929

#	Time	Username	Problem	Language	Result	Execution time	Memory
374929		BartolM	Building 4 (JOI20_building4)	C++17	100 / 100	333 ms	45536 KiB

building4

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <vector>
#include <cstring>
#include <cstdlib>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e6+5;

int n;
int A[N], B[N];
pii a[N], b[N];
string sol="";

pii mrg(pii a, pii b) {
    if (a.X<0) return b;
    if (b.X<0) return a;
    if (b.X-1 > a.Y || b.Y+1 < a.X) {
        assert(0);
    }
    pii res=a;
    if (b.X<res.X) res.X=b.X;
    if (b.Y>res.Y) res.Y=b.Y;
    return res;
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<2*n; ++i) scanf("%d", A+i);
    for (int i=0; i<2*n; ++i) scanf("%d", B+i);
}

void solve() {
    a[0]=mp(1, 1); b[0]=mp(0, 0);
//    printf("i==%d: [%d, %d], [%d, %d]\n", 0, 1, 1, 0, 0);
    for (int i=1; i<2*n; ++i) {

        a[i]=mp(-INF, -INF);
        b[i]=mp(-INF, -INF);

        if (B[i]>=B[i-1]) b[i]=mrg(b[i], b[i-1]);
        if (B[i]>=A[i-1]) b[i]=mrg(b[i], a[i-1]);

        if (A[i]>=A[i-1]) a[i]=mrg(a[i], mp(a[i-1].X+1, a[i-1].Y+1));
        if (A[i]>=B[i-1]) a[i]=mrg(a[i], mp(b[i-1].X+1, b[i-1].Y+1));
//        printf("i==%d: [%d, %d], [%d, %d]\n", i, a[i].X, a[i].Y, b[i].X, b[i].Y);
    }
    int mogua=0, mogub=0, cnt=n;
    if (a[2*n-1].X<=n && a[2*n-1].Y>=n) mogua=1;
    else if (b[2*n-1].X<=n && b[2*n-1].Y>=n) mogub=1;
    else {
        printf("-1\n");
        return;
    }
    for (int i=2*n-1; i>=0; --i) {
        if (mogua) {
            sol+='A';
            cnt--;
            mogua=0;
            mogub=0;
            if (!i) break;

            if (a[i-1].X<=cnt && a[i-1].Y>=cnt && A[i-1]<=A[i]) mogua=1;
            else mogub=1;
        }
        else {
            sol+='B';
            mogua=0;
            mogub=0;
            if (!i) break;

            if (a[i-1].X<=cnt && a[i-1].Y>=cnt && A[i-1]<=B[i]) mogua=1;
            else mogub=1;
        }

    }
    reverse(sol.begin(), sol.end());
    printf("%s\n", sol.c_str());
}

int main() {
    load();
    solve();
return 0;
}

Compilation message (stderr)

building4.cpp: In function 'void solve()':
building4.cpp:63:18: warning: variable 'mogub' set but not used [-Wunused-but-set-variable]
   63 |     int mogua=0, mogub=0, cnt=n;
      |                  ^~~~~
building4.cpp: In function 'void load()':
building4.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
building4.cpp:44:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     for (int i=0; i<2*n; ++i) scanf("%d", A+i);
      |                               ~~~~~^~~~~~~~~~~
building4.cpp:45:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     for (int i=0; i<2*n; ++i) scanf("%d", B+i);
      |                               ~~~~~^~~~~~~~~~~

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