Submission #260633

#	Time	Username	Problem	Language	Result	Execution time	Memory
260633		s0m30n3	건물 4 (JOI20_building4)	C++14	100 / 100	408 ms	45556 KiB

building4

#include<bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ppb pop_back
#define st first
#define nd second
#define ll long long
#define inf 100000000
#define MOD 998244353 
#define LOG 40
#define EPS 0.000000001
#define MAX 1000005
using namespace std;

int n;
pair<int, int> lr[MAX][2];
int c[2][MAX];

void no() {

	cout << -1;
	exit(0);

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	cin >> n;
	n <<= 1;
	for(int i = 0; i < 2; i++)
		for(int j = 1; j <= n; j++)
			cin >> c[i][j];
	lr[0][0] = lr[0][1] = {0, 0};
	for(int i = 1; i <= n; i++) {
		for(int plan_c = 0; plan_c < 2; plan_c++) { // 0 if a else 1
			lr[i][plan_c] = {inf, -inf};
			for(int plan_b = 0; plan_b < 2; plan_b++) {
				if(c[plan_c][i] >= c[plan_b][i - 1]) {
					lr[i][plan_c].st = min(lr[i][plan_c].st, lr[i - 1][plan_b].st + !plan_c);
					lr[i][plan_c].nd = max(lr[i][plan_c].nd, lr[i - 1][plan_b].nd + !plan_c);	
				}
			}
		}
	}
	int ind = n;
	int req = n / 2;
	string ans, _map = "AB";
	int last = 2;
	while(ind > 0) {
		for(int plan_c = 0; plan_c < 2; plan_c++) {
			if(lr[ind][plan_c].st <= req and lr[ind][plan_c].nd >= req) {
				if(!(last - 2) or c[last][ind + 1] >= c[plan_c][ind]) {
					ans.pb(_map[plan_c]);
					req -= (!plan_c);
					ind--;
					last = plan_c;
					break ;
				}
			}
			if(plan_c == 1)
				no();
		}	
	}
	reverse(ans.begin(), ans.end());
	cout << ans;

}

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