Submission #866127

#	Time	Username	Problem	Language	Result	Execution time	Memory
866127		phoenix0423	Building 4 (JOI20_building4)	C++17	100 / 100	187 ms	57416 KiB

building4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 1e6 + 5;
const int INF = 1e9;
int n, Q;
int dpl[maxn][2], dpr[maxn][2]; // # of A used

int main(void){
	fastio;
	int n;
	cin>>n;
	n *= 2;
	vector<int> a(n), b(n), no(n), no2(n), ou(n);
	for(int i = 0; i < n; i++) cin>>a[i];
	for(int i = 0; i < n; i++) cin>>b[i];
	// type 0 : 2, 2 / type 1 : 2, 1 / type 2 : 1, 1 / type 3 : 1, 0
	dpl[0][0] = dpr[0][0] = 1;
	dpl[0][1] = dpr[0][1] = 0;
	for(int i = 1; i < n; i++){
		dpl[i][0] = dpl[i][1] = INF;
		dpr[i][0] = dpr[i][1] = -1;
		if(a[i - 1] <= a[i]) dpl[i][0] = dpl[i - 1][0] + 1, dpr[i][0] = dpr[i - 1][0] + 1;
		if(b[i - 1] <= a[i]) ckmin(dpl[i][0], dpl[i - 1][1] + 1), ckmax(dpr[i][0], dpr[i - 1][1] + 1);
		if(b[i - 1] <= b[i]) dpl[i][1] = dpl[i - 1][1], dpr[i][1] = dpr[i - 1][1];
		if(a[i - 1] <= b[i]) ckmin(dpl[i][1], dpl[i - 1][0]), ckmax(dpr[i][1], dpr[i - 1][0]);
	}
	int bad = 0;
	if(dpl[n - 1][0] > n / 2 && dpl[n - 1][1] > n / 2) bad = 1;
	if(dpr[n - 1][0] < n / 2 && dpr[n - 1][1] < n / 2) bad = 1;
	if(bad){
		cout<<-1<<"\n";
		return 0;
	}
	int pos = 0;
	if(dpl[n - 1][1] <= n / 2 && dpr[n - 1][1] >= n / 2) pos = 1;
	string ans = "";
	ans += char('A' + pos);
	int need = n / 2 - 1 + pos;
	for(int i = n - 2; i >= 0; i--){
		if(dpl[i][0] <= need && dpr[i][0] >= need && a[i] <= (pos ? b[i + 1] : a[i + 1])) pos = 0;
		else pos = 1;
		ans += char('A' + pos);
		need = need - 1 + pos;
	}
	reverse(ans.begin(), ans.end());
	cout<<ans<<"\n";
}

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