Submission #894739

#	Time	Username	Problem	Language	Result	Execution time	Memory
894739		beaboss	Building 4 (JOI20_building4)	C++14	100 / 100	185 ms	42020 KiB

building4

// Source: https://oj.uz/problem/view/JOI20_building4
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = (5e5 + 10) * 2;

int a[N];
int b[N];
int c[N];
int oc[N];

int swaps[N]; // -1 if not possible, 1 if dependent, 2 if independent

int cnt = 0;

bool flipped=false;

int n;

char rev(char ff) {
	if (ff == 'A') {
		cnt--;
		return 'B';
	}
	else {
		cnt++;
		return 'A';
	}
}
string chk(string s) {
	if (flipped) {
		FOR(i, 0, n) s[i] = rev(s[i]);
	}

	int prv = -1;

	FOR(i, 0, n) {
		if (s[i] == 'A') {
			assert(a[i] >= prv);
			prv = a[i];
		} else {
			assert(b[i] >= prv);
			prv = b[i];
		}
	}

	return s;
}

// int count(string s, char c) {
// 	int res = 0;
// 	FOR(i, 0, n) if (c == s[i]) res++;
// 	return res;
// }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	
	cin >> n;

	n *= 2;

	FOR(i, 0, n) {
		cin >> a[i];
	}
	FOR(i, 0, n) cin >> b[i];

	string ans;

	c[0] = min(a[0], b[0]);
	oc[0] = max(a[0], b[0]);

	if (c[0] == a[0]) {
		cnt++;
		ans += 'A';
	}
	else ans += 'B';

	for (int i = 1; i < n; i++) {
		if (min(a[i], b[i]) >= c[i-1]) {
			c[i] = min(a[i], b[i]);
			oc[i] = max(a[i], b[i]);
		} else if (max(a[i], b[i]) >= c[i-1]) {
			swaps[i]=-1;
			c[i] = max(a[i], b[i]);
			oc[i] = min(a[i], b[i]);

		} else {
			cout << -1 << endl;
			return 0;
		}

		if (c[i] == a[i]) {
			cnt++;
			ans += 'A';
		}
		else ans += 'B';
	}

	if (cnt == n/2) {
		cout << ans << endl;
		return 0;
	}


	
	if (cnt > n/2) {
		flipped=true;
		FOR(i, 0, n) ans[i] = rev(ans[i]);
	}


	c[n] = 1e9 + 10;
	// cout << cnt << endl;
	for (int i = n-1; i >= 0; i--) {
		
		assert(c[i] <= c[i+1]);
		if (swaps[i] == -1) continue;
		if (oc[i] <= c[i + 1]) swaps[i]=2; // independent
		else if (swaps[i + 1] != -1 && oc[i] <= oc[i + 1]) swaps[i]=1; // dependent
		else swaps[i]=-1;

		// cout << i << swaps[i] << endl;
	}




	int st = n-1;
	int mx = -1;
	int pos = -1;
	int res = 0;


	// assumes that A has less frequency

	for (int i = n-1; i >= 0; i--) {
		// cout << i << st << swaps[i] << endl;

		if (swaps[i] == -1 || swaps[i] == 2) {
			// cout << st << pos << mx << endl;
			if (i != st) {
				if (mx != -1) {
					// cout << pos << endl;
					for (int j = st; j >= pos; j--) {

						if (cnt != n/2) ans[j] = rev(ans[j]);
						else {
							cout << chk(ans) << endl;
							return 0;
						}

						if (cnt == n/2) {
							cout << chk(ans) << endl;
							return 0;
						}

					}
				}
			}
			st = i-1;
			mx = -1;
			res=0;

		}

		if (swaps[i] == 2) {
			st = i;
		}

		if (swaps[i] != -1) {
			res -= (ans[i] == 'A');
			res += (ans[i] == 'B');
			// cout << i << res << endl;
			if (res > mx) {
				pos = i;
				mx = res;
			}
		}

		// cout << i << st << mx <<  res << ans[i] << endl;
	}
	// cout << ans << endl;
	// cout << pos << endl;
	if (0 <= st && pos != -1) {
		for (int j = st; j >= pos; j--) {
			if (cnt != n/2) ans[j] = rev(ans[j]);
			else {
				cout << chk(ans) << endl;
				return 0;
			}

			if (cnt == n/2) {
				cout << chk(ans) << endl;
				return 0;
			}
		}
	}

	if (cnt == n/2) cout << chk(ans) << endl;

	else {

		cout << -1 << endl;
		// assert(false);
		return 0;
	}




}

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