Submission #281524

#	Time	Username	Problem	Language	Result	Execution time	Memory
281524		shoemakerjo	Building 4 (JOI20_building4)	C++14	100 / 100	327 ms	48280 KiB

building4

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pii pair<int, int>
#define pll pair<ll, ll>


int n;
const int maxn = 1000010;

int a[maxn];
int b[maxn];

pii rg[maxn][2];

int res[maxn]; //0 for A, 1 for B

pii urange(pii u, pii v) {
	if (u.first == -1) return v;
	if (v.first == -1) return u;
	return {min(u.first, v.first), max(u.second, v.second)};
}

bool isin(int val, pii br) {
	return val >= br.first && val <= br.second;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= 2*n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= 2*n; i++) {
		cin >> b[i];
	}

	// set A initial values to be 1 of each
	rg[1][0] = {1, 1};
	rg[1][1] = {0, 0};

	for (int i = 2; i <= 2*n; i++) {
		rg[i][0] = {-1, -1};
		rg[i][1] = {-1, -1};

		if (a[i-1] <= a[i]) {
			rg[i][0] = urange(rg[i][0], rg[i-1][0]);
		}
		if (b[i-1] <= a[i]) {
			rg[i][0] = urange(rg[i][0], rg[i-1][1]);
		}
		if (a[i-1] <= b[i]) {
			rg[i][1] = urange(rg[i][1], rg[i-1][0]);
		}
		if (b[i-1] <= b[i]) {
			rg[i][1] = urange(rg[i][1], rg[i-1][1]);
		}
		if (rg[i][0].first != -1) {
			rg[i][0] = {rg[i][0].first+1, rg[i][0].second+1};
		}

		// cout << i << " : " << rg[i][0].first << " " << rg[i][0].second 
			// << " -- " << rg[i][1].first << " " << rg[i][1].second << endl;
	}	

	int indo = -1;
	if (isin(n, rg[2*n][0])) indo = 0;
	if (isin(n, rg[2*n][1])) indo = 1;

	res[2*n] = indo;
	if (indo == -1) {
		cout << -1 << endl;
		return 0;
	}
	int ctarg = n;

	for (int i = 2*n-1; i >= 1; i--) {
		if (indo == 0) ctarg--;
		int nindo = -1;
		int cval = a[i+1];
		if (indo == 1) cval = b[i+1];
		if (isin(ctarg, rg[i][0]) && a[i] <= cval) {
			nindo = 0;
		}
		else nindo = 1;
		indo = nindo;
		res[i] = indo;
	}

	for (int i = 1; i <= 2*n; i++) {
		if (res[i] == 0) cout << "A";
		else cout << "B";
	}
	cout << endl;

}

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