제출 #1008176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008176		vako_p	건물 4 (JOI20_building4)	C++14	100 / 100	187 ms	68920 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,a[mxN],b[mxN];
pair<ll,ll> A[mxN],B[mxN];
char ans[mxN];

void rec(ll i, ll k, ll x){
	if(i == 0) return;
//	cout << i << ' ' << ((x == 0) ? a[i] : b[i]) << ' ' << a[i - 1] << ' ' << x << '\n';
	if(k > 0 and A[i - 1].first <= k and A[i - 1].second >= k and a[i - 1] <= ((x == 0) ? a[i] : b[i])){
 		ans[i - 1] = 'A';
		rec(i - 1, k - 1, 0); 
	}
	else{
		ans[i - 1] = 'B';
		rec(i - 1, k, 1); 
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 0; i < 2 * n; i++) cin >> a[i];
	for(int i = 0; i < 2 * n; i++) cin >> b[i];
	A[0] = {1, 1};
	B[0] = {0, 0};
	for(int i = 1; i < 2 * n; i++){
		A[i].first = 1e9;
		A[i].second = -1;
		if(a[i] >= a[i - 1]) A[i] = {A[i - 1].first + 1, A[i - 1].second + 1};
		if(a[i] >= b[i - 1]) A[i] = {min(A[i].first, B[i - 1].first + 1), max(A[i].second, B[i - 1].second + 1)};
		B[i].first = 1e9;
		B[i].second = -1;
		if(b[i] >= b[i - 1]) B[i] = {B[i - 1].first, B[i - 1].second};
		if(b[i] >= a[i - 1]) B[i] = {min(B[i].first, A[i - 1].first), max(B[i].second, A[i - 1].second)};
 		if(A[i].second == -1 and B[i].second == -1){
 			cout << -1;
 			return 0;
		}
//		cout << A[i].first << ' ' << A[i].second << ' ' << B[i].first << ' ' << B[i].second << '\n';
	}
 	if(A[2 * n - 1].first <= n and A[2 * n - 1].second >= n){
 		ans[2 * n - 1] = 'A';
		rec(2 * n - 1, n - 1, 0); 
		for(int i = 0; i < 2 * n; i++) cout << ans[i];
	}
	else if(B[2 * n - 1].first <= n and B[2 * n - 1].second >= n){
		ans[2 * n - 1] = 'B';
		rec(2 * n - 1, n, 1); 
		for(int i = 0; i < 2 * n; i++) cout << ans[i];
	}
	else cout << -1;	
}

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