제출 #1166306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166306		MPG	건물 4 (JOI20_building4)	C++20	100 / 100	151 ms	49500 KiB

building4

//#pragma GCC optomize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define     max_heap priority_queue<pair <ll, pair <ll, ll>>>
//#define     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define     min_heap priority_queue<pair <ll, pair <ll, ll>>, vector<pair <ll, pair <ll, ll>>>, greater<pair <ll, pair <ll, ll>>>>

#define     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define     filE freopen("in.txt", "r", stdin);// freopen("out1.txt", "w", stdout); 
#define     endl '\n'
#define     md(a) (a % mod + mod) % mod
#define     pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769


ll const maxn = 1e6 + 123;
ll const inf = 3e18;
ll const loG = 18; // 23
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}


ll n, arr[maxn][2], mx[maxn][2], mn[maxn][2];
string s;

void Solve(){

cin >> n;
for(int i = 1; i < 2 * n + 1; i++)
    cin >> arr[i][0];
for(int i = 1; i < 2 * n + 1; i++)
    cin >> arr[i][1];
for(int i = 1; i <= 2 * n; i++) {
    mx[i][0] = mx[i][1] = -inf;
    mn[i][0] = mn[i][1] = inf;
}
for(int i = 1; i <= 2 * n; i++) {
    if (arr[i][0] >= arr[i - 1][0]){
        mx[i][0] = max(mx[i - 1][0], mx[i][0]);
        mn[i][0] = min(mn[i - 1][0], mn[i][0]);
    }
    if (arr[i][1] >= arr[i - 1][0]){
        mx[i][1] = max(mx[i][1], mx[i - 1][0] + 1);
        mn[i][1] = min(mn[i][1], mn[i - 1][0] + 1);
    }
    if (arr[i][0] >= arr[i - 1][1]){
        mx[i][0] = max(mx[i - 1][1], mx[i][0]);
        mn[i][0] = min(mn[i - 1][1], mn[i][0]);
    }
    if (arr[i][1] >= arr[i - 1][1]){
        mx[i][1] = max(mx[i][1], mx[i - 1][1] + 1);
        mn[i][1] = min(mn[i][1], mn[i - 1][1] + 1);
    }
}
ll chi;
if (mn[2 * n][0] <= n && mx[2 * n][0] >= n)
    chi = 0;
else if (mn[2 * n][1] <= n && mx[2 * n][1] >= n)
    chi = 1;
else{
    cout << -1 << endl;
    return;
}
ll bag = n;
for (int i = 2 * n - 1; i >= 0; i--){
    if (chi)
        s.pb('B');
    else
        s.pb('A');
    bag -= chi;
    if ( (mx[i][chi] < bag) || (mn[i][chi] > bag) || ((i > 1) && (arr[i + 1][chi] < arr[i][chi])))
        chi = 1 - chi;
}
reverse(s.begin(), s.end());
cout << s << endl;




}



int main(){
sariE;
//filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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