Submission #560970

#	Time	Username	Problem	Language	Result	Execution time	Memory
560970		Mazaalai	Building 4 (JOI20_building4)	C++17	0 / 100	0 ms	212 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() {
	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; a[2*n+1] = INF;
	b[0] = 0; b[2*n+1] = 0;
	int cur = 0, A = 1, B = 0, tar = n+1;
	bool swapped = 0;
	for (int i = 2*n+1; i > 0; i--) {
		if (cur == 0) {
			if (a[i] < min(a[i-1], b[i-1])) {
				if (swapped) {
					cout << "-1\n";
					return 0;
				}
				A--;
				B++;
				swapped = 1;
				cur ^= 1;
				i++;
				continue;
			}
			if (a[i-1] > a[i]) ans[i-1] = 1;
		} else {
			if (b[i] < min(a[i-1], b[i-1])) {
				if (swapped) {
					cout << "-1\n";
					return 0;
				}
				B--;
				A++;
				swapped = 1;
				cur ^= 1;
				i++;
				continue;
			}
			if (a[i-1] > b[i]) ans[i-1] = 1;
		}
		cur = ans[i];
		A += cur == 0;
		B += cur == 1;
		swapped = 0;
	}
	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:57:7: warning: unused variable 'y' [-Wunused-variable]
   57 |   int y = (ans[i] ? b[i] : a[i]);
      |       ^
building4.cpp:70:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |  for (int i = 1; i <= 2*n; i++) cout << (ans[i] ? 'B' : 'A'); cout <<'\n';
      |  ^~~
building4.cpp:70:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   70 |  for (int i = 1; i <= 2*n; i++) cout << (ans[i] ? 'B' : 'A'); cout <<'\n';
      |                                                               ^~~~
building4.cpp:16:29: warning: unused variable 'tar' [-Wunused-variable]
   16 |  int cur = 0, A = 1, B = 0, tar = n+1;
      |                             ^~~

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