oj.uz

Submission #894711

# Submission time Handle Problem Language Result Execution time Memory
894711 2023-12-28T18:40:44 Z beaboss Building 4 (JOI20_building4) C++14
0 / 100
 8 ms 17240 KB 
// 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 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;

	for (int i = n-1; i >= 0; i--) {
		if (swaps[i] == -1) continue;
		assert(c[i] <= c[i+1]);
		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;
	}




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


	// assumes that A has less frequency

	for (int i = n-1; i >= 0; i--) {
		if (swaps[i] == -1 || swaps[i] == 2) {
			if (i != st) {
				if (mx == -1) continue;
				for (int j = st; j >= pos; j--) {

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

				}
			}
			st = i-1;
		}

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

		if (swaps[i] != -1) {
			res -= (ans[i] == 'A');
			res += (ans[i] == 'B');

			if (res > mx) {
				pos = i;
				mx = res;
			}
		}

		// cout << i << st << mx <<  res << ans[i] << endl;
	}

	if (0 <= st) {
		for (int j = st; j >= 0; 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;

	else cout << -1 << endl;




}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8692 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Runtime error 8 ms 17240 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8692 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Runtime error 8 ms 17240 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -