Submission #379497

#	Time	Username	Problem	Language	Result	Execution time	Memory
379497		Jarif_Rahman	Building 4 (JOI20_building4)	C++17	100 / 100	312 ms	44512 KiB

building4

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9 + 9;
bool inside(pair<int, int> a, int p){
    return (p >= a.f && p <= a.sc);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<int> a(2*n), b(2*n);
    for(int &x: a) cin >> x;
    for(int &x: b) cin >> x;
    vector<pair<int, int>> dpa(2*n), dpb(2*n);
    dpa[0] = {1, 1};
    dpb[0] = {0, 0};
    for(int i = 1; i < 2*n; i++){
        auto [al, ar] = dpa[i-1];
        auto [bl, br] = dpb[i-1];
        {
            int l1 = -1, r1 = -1, l2 = -1, r2 = -1;
            if(a[i] >= a[i-1] && al != -1) l1 = al+1, r1 = ar+1;
            if(a[i] >= b[i-1] && bl != -1) l2 = bl+1, r2 = br+1;
            if(l1 == -1 && l2 == -1){
                dpa[i] = {-1, -1};
            }
            else if(l1 == -1){
                dpa[i] = {l2, r2};
            }
            else if(l2 == -1){
                dpa[i] = {l1, r1};
            }
            else{
                if(l1 > l2) swap(l1, l2), swap(r1, r2);
                dpa[i] = {min(l1, l2), max(r1, r2)};
            }
        }
        {
            int l1 = -1, r1 = -1, l2 = -1, r2 = -1;
            if(b[i] >= a[i-1] && al != -1) l1 = al, r1 = ar;
            if(b[i] >= b[i-1] && bl != -1) l2 = bl, r2 = br;
            if(l1 == -1 && l2 == -1){
                dpb[i] = {-1, -1};
            }
            else if(l1 == -1){
                dpb[i] = {l2, r2};
            }
            else if(l2 == -1){
                dpb[i] = {l1, r1};
            }
            else{
                if(l1 > l2) swap(l1, l2), swap(r1, r2);
                dpb[i] = {min(l1, l2), max(r1, r2)};
            }
        }
    }
    if(!inside(dpa[2*n-1], n) && !inside(dpb[2*n-1], n)){
        cout << "-1\n";
        exit(0);
    }
    str ans = "";
	str cur;
	if(inside(dpa[2*n-1], n)) cur = "A";
	else cur = "B";
	int cnt = n;
    for(int i = 2*n-1; i >= 0; i--){
		ans+=cur;
		if(cur == "A") cnt--;
		if(i > 0){
			if(inside(dpa[i-1], cnt) && (cur == "A" ? a:b)[i] >= a[i-1]) cur = "A";
			else cur = "B";
		}
    }
	reverse(ans.begin(), ans.end());
	cout << ans << "\n";
}

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