Submission #1126425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126425		TAhmed33	Building 4 (JOI20_building4)	C++20	0 / 100	1 ms	328 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
typedef long double ld;
const int MAXN = 1e6 + 25;
int n, a[MAXN][2], c[MAXN];
void solve () {
	cin >> n; n *= 2;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][0];
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i][1];
	}
	int prv = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i][0] >= prv && a[i][1] >= prv) {
			if (a[i][0] <= a[i][1]) {
				c[i] = 0;
				prv = a[i][0];
			} else {
				c[i] = 1;
				prv = a[i][1];
			}
		} else if (a[i][0] >= prv) {
			c[i] = 0;
			prv = a[i][0];
		} else if (a[i][1] >= prv) {
			c[i] = 1;
			prv = a[i][1];
		} else {
			cout << "-1\n";
			return;
		}
	}
/*	for (int i = 1; i <= n; i++) {
		cout << c[i] << " ";
	}
	cout << '\n';*/
	int cnt[2] = {};
	for (int i = 1; i <= n; i++) {
		cnt[c[i]]++;
	}
	if (cnt[0] < cnt[1]) {
		for (int i = n; i >= 1 && cnt[0] < cnt[1]; i--) {
			if ((c[i] == 1) && ((i == 1 || a[i][0] >= a[i - 1][c[i - 1]]) && (i == n || a[i][0] <= a[i + 1][c[i + 1]]))) {
				c[i] ^= 1; cnt[1]--; cnt[0]++;
			} else if (c[i] != c[i - 1] && a[i - 1][1 - c[i - 1]] <= a[i][1 - c[i]] && a[i - 1][c[i - 1]] <= a[i - 1][1 - c[i - 1]]) {
				c[i] ^= 1; c[i - 1] ^= 1;
			}
		}
	} else if (cnt[0] > cnt[1]) {
		for (int i = n; i >= 1 && cnt[0] > cnt[1]; i--) {
			if ((c[i] == 0) && ((i == 1 || a[i][1] >= a[i - 1][c[i - 1]]) && (i == n || a[i][1] <= a[i + 1][c[i + 1]]))) {
				c[i] ^= 1; cnt[1]++; cnt[0]--;
			} else if (c[i] != c[i - 1] && a[i - 1][1 - c[i - 1]] <= a[i][1 - c[i]] && a[i - 1][c[i - 1]] <= a[i - 1][1 - c[i - 1]]) {
				c[i] ^= 1; c[i - 1] ^= 1;
			}
		}
	}
	if (cnt[0] != cnt[1]) {
		cout << "-1\n";
		return;
	}
	char v[2] = {'A', 'B'};
	for (int i = 1; i <= n; i++) {
		cout << v[c[i]];
	}
	cout << '\n';
}				
signed main () {
/*	#ifndef ONLINE_JUDGE 
		freopen("input_file", "r", stdin);
		freopen("output_file", "w", stdout);
	#endif*/
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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