Submission #896619

#	Time	Username	Problem	Language	Result	Execution time	Memory
896619		Andrey	Building 4 (JOI20_building4)	C++14	100 / 100	182 ms	45388 KiB

building4

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(2*n+1);
    vector<int> b(2*n+1);
    vector<pair<int,int>> wow(2*n+1,{1e9,0});
    vector<pair<int,int>> wut(2*n+1,{1e9,0});
    for(int i = 1; i <= 2*n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= 2*n; i++) {
        cin >> b[i];
    }
    wow[0] = {0,0};
    wut[0] = {0,0};
    for(int i = 1; i <= 2*n; i++) {
        if(a[i] >= a[i-1]) {
            wow[i] = {wow[i-1].first+1,wow[i-1].second+1};
        }
        if(a[i] >= b[i-1]) {
            wow[i] = {min(wow[i].first,wut[i-1].first+1),max(wow[i].second,wut[i-1].second+1)};
        }
        if(b[i] >= a[i-1]) {
            wut[i] = {wow[i-1].first,wow[i-1].second};
        }
        if(b[i] >= b[i-1]) {
            wut[i] = {min(wut[i].first,wut[i-1].first),max(wut[i].second,wut[i-1].second)};
        }
    }
    string ans = "";
    int x = -1,br = n;
    if(wow[2*n].second >= n && wow[2*n].first <= n) {
        x = 0;
        ans = "A";
        br--;
    }
    else if(wut[2*n].second >= n && wut[2*n].first <= n) {
        x = 1;
        ans = "B";
    }
    if(x == -1) {
        cout << -1 << "\n";
    }
    else {
        for(int i = 2*n-1; i >= 1; i--) {
            int c;
            if(x == 0) {
                c = a[i+1];
            }
            else {
                c = b[i+1];
            }
            if(wow[i].second >= br && wow[i].first <= br && a[i] <= c) {
                ans+='A';
                x = 0;
                br--;
            }
            else {
                ans+='B';
                x = 1;
            }
        }
        reverse(ans.begin(),ans.end());
        cout << ans;
    }

    return 0;
}

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