Submission #768386

#	Time	Username	Problem	Language	Result	Execution time	Memory
768386		minhcool	Building 4 (JOI20_building4)	C++17	100 / 100	203 ms	64672 KiB

building4

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n, a[N], b[N];
 
int maxia[N][2], maxib[N][2];
 
#ifdef local
void process(){
	cin >> n;
	for(int i = 1; i <= 2 * n; i++) cin >> a[i];
	for(int i = 1; i <= 2 * n; i++) cin >> b[i];
	for(int i = 1; i <= 2 * n; i++) maxia[i][0] = maxia[i][1] = maxib[i][0] = maxib[i][1] = -oo;
	maxia[2 * n][0] = maxib[2 * n][1] = 1;
	maxia[2 * n][1] = maxib[2 * n][0] = 0;
	for(int i = 2 * n - 1; i >= 1; i--){
		for(int j = 0; j < 2; j++){
			for(int lst = 0; lst < 2; lst++){
				int temp1 = (!j ? a[i] : b[i]);
				int temp2 = (!lst ? a[i + 1] : b[i + 1]);
				if(temp1 > temp2) continue;
				maxia[i][j] = max(maxia[i][j], maxia[i + 1][lst] + (j == 0));
				maxib[i][j] = max(maxib[i][j], maxib[i + 1][lst] + (j == 1));
			}
		//	cout << i << " " << j << " " << maxia[i][j] << " " << maxib[i][j] << "\n";
		}
	}
	int temp = -1;
	if(maxia[1][0] >= n && maxib[1][0] >= n) temp = 0;
	if(maxia[1][1] >= n && maxib[1][1] >= n) temp = 1;
	if(temp < 0){
		cout << -1 << "\n";
		return;
	}
	string s;
	int aa = (temp == 0), bb = (temp == 1), lst = temp;
	if(temp == 0) s += "A";
	else s += "B";
	for(int i = 2; i <= 2 * n; i++){
		int tempo = (lst == 0 ? a[i - 1] : b[i - 1]);
		if(a[i] < tempo){
			bb++;
			lst = 1;
			s += "B";
		}
		else if(b[i] < tempo){
			aa++;
			lst = 0;
			s += "A";
		}
		else if((maxia[i][0] >= n - aa) && (maxib[i][0] >= n - bb)){
			aa++;
			lst = 0;
			s += "A";
		}
		else{
			bb++;
			lst = 1;
			s += "B";
		}
	}
	cout << s;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

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