Submission #560981

#	Time	Username	Problem	Language	Result	Execution time	Memory
560981		Mazaalai	Building 4 (JOI20_building4)	C++17	0 / 100	4 ms	340 KiB

building4

#include <bits/stdc++.h>

using namespace std;

int n;
const int N = 5e5 + 5;
const int M = 2 * N;
int a[M], b[M], ans[M]; // 0 ? A : B
const int INF = 1.07e9;
signed main() {
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= 2 * n; i++) cin >> a[i];
	for (int i = 1; i <= 2 * n; i++) cin >> b[i];

	a[0] = INF-1; a[2*n+1] = INF-1;
	b[0] = 0; b[2*n+1] = 0;
	for (int i = 1; i <= 2 * n; i++) {
		if (a[i] < a[i-1] && a[i] < b[i-1]) a[i] = INF;
		if (b[i] < a[i-1] && b[i] < b[i-1]) b[i] = INF;
	}
	// for (int i = 1; i <= 2 * n; i++) cout << a[i] << " \n"[i==2*n];
	// for (int i = 1; i <= 2 * n; i++) cout << b[i] << " \n"[i==2*n];
	int A = 0, B = 0, tar = n+1;
	for (int i = 2*n+1; i > 0; i--) {
		if ((ans[i] == 0 && a[i] == INF) || (ans[i] == 1 && b[i] == INF)) {
			// cout << i << ' ' << ans[i] << '\n';
			cout << "-1\n";
			return 0;
		}
		if (ans[i] == 0) {
			if (a[i] < min(a[i-1], b[i-1])) {
				cout << "-1\n";
				return 0;
			}
			// cout << "HERE: " << a[i-1] << ' ' << a[i] << '\n';
			if (a[i-1] > a[i]) ans[i-1] = 1;
		} else {
			if (b[i] < min(a[i-1], b[i-1])) {
				cout << "-1\n";
				return 0;
			}
			if (a[i-1] > b[i]) ans[i-1] = 0;
		}
		A += ans[i] == 0;
		B += ans[i] == 1;
	}
	A += ans[0] == 0;
	B += ans[0] == 1;
	int i = 2*n;
	while (A > B && i > 1) { 
		i--;
		int x = (ans[i-1] ? b[i-1] : a[i-1]);
		int y = (ans[i] ? b[i] : a[i]);
		int z = (ans[i+1] ? b[i+1] : a[i+1]);
		if (ans[i] == 1) continue;
		if (x <= b[i] && b[i] <= z) {
			ans[i] = 1;
			A--;
			B++;
		}
	}
	if (A != B) {
		cout <<"-1\n";
		return 0;
	}
	for (int i = 1; i <= 2*n; i++) cout << (ans[i] ? 'B' : 'A'); cout <<'\n';

}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:55:7: warning: unused variable 'y' [-Wunused-variable]
   55 |   int y = (ans[i] ? b[i] : a[i]);
      |       ^
building4.cpp:68:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   68 |  for (int i = 1; i <= 2*n; i++) cout << (ans[i] ? 'B' : 'A'); cout <<'\n';
      |  ^~~
building4.cpp:68:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   68 |  for (int i = 1; i <= 2*n; i++) cout << (ans[i] ? 'B' : 'A'); cout <<'\n';
      |                                                               ^~~~
building4.cpp:25:20: warning: unused variable 'tar' [-Wunused-variable]
   25 |  int A = 0, B = 0, tar = n+1;
      |                    ^~~

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