제출 #235205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235205		AMO5	건물 4 (JOI20_building4)	C++98	100 / 100	321 ms	44908 KiB

building4

#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007
 
typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
 
ll INF=LLONG_MAX;
 
int const mxn = 1e6+5;
int dp[mxn][2][2]; //pos, cur, min/max = cnt of b;
int a[mxn],b[mxn];

void mins(int &a, int b){
	a = min(a,b);
	return;
}

void maxs(int &a, int b){
	a = max(a,b);
	return;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	memset(dp,-1,sizeof(dp));
	for(int i=1; i<=n*2; i++)cin >> a[i];
	for(int i=1; i<=n*2; i++)cin >> b[i];
	dp[1][0][0] = dp[1][0][1] = 0;
	dp[1][1][0] = dp[1][1][1] = 1;
	for(int i=2; i<=n*2; i++){
		dp[i][0][0]=dp[i][1][0] = mxn;
		dp[i][0][1]=dp[i][1][1] = -1;
		if(a[i]>=a[i-1]){
			mins(dp[i][0][0],dp[i-1][0][0]);
			maxs(dp[i][0][1],dp[i-1][0][1]);
		}
		if(a[i]>=b[i-1]){
			mins(dp[i][0][0],dp[i-1][1][0]);
			maxs(dp[i][0][1],dp[i-1][1][1]);
		}
		if(b[i]>=a[i-1]){
			mins(dp[i][1][0],dp[i-1][0][0]+1);
			maxs(dp[i][1][1],dp[i-1][0][1]+1);
		}
		if(b[i]>=b[i-1]){
			mins(dp[i][1][0],dp[i-1][1][0]+1);
			maxs(dp[i][1][1],dp[i-1][1][1]+1);
		}
	}
	bool cur=0; int cnt=n;
	if(dp[n*2][0][0]<=n&&n<=dp[n*2][0][1])cur = 0;
	else if(dp[n*2][1][0]<=n&&n<=dp[n*2][1][1])cur = 1;
	else{
		cout << -1 << endl;
		return 0;
	}
	//start backtracking
	string s="";
	for(int i=n*2; i>=1; i--){
		if(!cur){
			s+='A';
			if(a[i-1]<=a[i]&&dp[i-1][0][0]<=cnt&&cnt<=dp[i-1][0][1])cur = 0;
			if(b[i-1]<=a[i]&&dp[i-1][1][0]<=cnt&&cnt<=dp[i-1][1][1])cur = 1; 
		}else{
			s+='B';
			cnt--;
			if(a[i-1]<=b[i]&&dp[i-1][0][0]<=cnt&&cnt<=dp[i-1][0][1])cur = 0;
			if(b[i-1]<=b[i]&&dp[i-1][1][0]<=cnt&&cnt<=dp[i-1][1][1])cur = 1; 
		}
	}
	reverse(all(s));
	cout << s << endl;
}	

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