제출 #930662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930662		KiaRez	건물 4 (JOI20_building4)	C++17	100 / 100	202 ms	45488 KiB

building4

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 1e6+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, a[N], b[N];
pii dp[2][N];
string str;

pii merge(pii v, pii u) {
	return Mp(min(v.F, u.F), max(v.S, u.S));
}

void solve(int bt, int id, int cnt) {
	if(id==0) return;

	if(bt==1)str.pb('B');
	else str.pb('A');
	
	if(bt==0) {
		if(a[id]>=a[id-1] && dp[0][id-1].F<=(n/2-cnt-1) && dp[0][id-1].S>=(n/2-cnt-1)) {
			solve(0, id-1, cnt+1);
			return;
		}
		solve(1, id-1, cnt+1);
	} else {
		if(b[id]>=a[id-1] && dp[0][id-1].F<=(n/2-cnt) && dp[0][id-1].S>=(n/2-cnt)) {
			solve(0, id-1, cnt);
			return;
		}
		solve(1, id-1, cnt);
	}
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n; n*=2;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i++) cin>>b[i];
	dp[0][0] = dp[1][0] = {0, 0};

	for(int i=1; i<=n; i++) {
		dp[0][i] = dp[1][i] = {1e9, -1e9};
		if(a[i]>=a[i-1] && a[i]>=b[i-1]) dp[0][i] = merge(dp[0][i-1], dp[1][i-1]);
		else if(a[i]>=a[i-1]) dp[0][i] = dp[0][i-1];
		else if(a[i]>=b[i-1]) dp[0][i] = dp[1][i-1];
		dp[0][i].F++, dp[0][i].S++;
		
		if(b[i]>=a[i-1] && b[i]>=b[i-1]) dp[1][i] = merge(dp[0][i-1], dp[1][i-1]);
		else if(b[i]>=a[i-1]) dp[1][i] = dp[0][i-1];
		else if(b[i]>=b[i-1]) dp[1][i] = dp[1][i-1];
	}

	if(dp[0][n].F<=n/2 && dp[0][n].S>=n/2) {
		solve(0, n, 0);
	} else if(dp[1][n].F<=n/2 && dp[1][n].S>=n/2) {
		solve(1, n, 0);
	} else {
		kill(-1);
	}
	reverse(all(str));
	cout<<str<<endl;

	return 0;
}

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