제출 #1229351

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

building4

#define Magic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long long double
#define en '\n'
#define tsts int tetss; cin >> tetss; while(tetss--)
#define all(a) a.begin() , a.end()
#define pb push_back
#define ld long long double
#define fi first
#define se second
ll INF = 1e18;
const int N = 4e5 + 1;
const int mod = 998244353;
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; 
 
// order_of_key(n) - The number of items in a set that are strictly smaller than k
// find_by_order(k) - It returns an iterator to the ith largest element
 
ll lcm(ll a, ll b)
{
  ll gc = __gcd(a, b);
  return   a / gc * b;
}
 
ll binpow (ll a, ll n) {
  if (n == 0)
    return 1;
  if (n % 2 == 1)
    return binpow (a, n-1) * a;
  else {
    ll b = binpow (a, n/2);
    return b * b;
  }
}
 
 
ll binpow_mod(ll a, ll b, ll md)
{
    ll res = 1;
    a = a % md;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % md;
        a = (a * a) % md;
        b >>= 1;
    }
    return res;
}
 
ll in() {ll x; cin >> x; return x;};
 
ll gcd (ll a, ll b, ll & x, ll & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	ll x1, y1;
	ll d = gcd (b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}
 
ll gcdinv(ll a, ll b){
	ll x, y;
	gcd(a, b, x, y);
	return x;
}
 
ll eql(ll x, ll y, bool ok){
	if(ok) return x;
	else return y;
}
 
// -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- чё
ll a[1000012][2];
ll dp1[1000012][2];
ll dp2[1000012][2];

void solve(){
	ll n; cin >> n;
	for(ll i = 1; i <= n * 2; ++i) cin >> a[i][0];
	for(ll i = 1; i <= n * 2; ++i) cin >> a[i][1];
	for(ll i = 1; i <= 2 * n; ++i){
		for(ll j = 0; j < 2; ++j){
			dp1[i][j] = -INF;
			dp2[i][j] = INF;
		}
	}
	dp1[n * 2][1] = dp2[n * 2][1] = 1;
	dp1[n* 2][0] = dp2[n * 2][0] = 0;
	for(ll i = n * 2; i > 1; --i){
		for(ll j = 0; j < 2; ++j){
			for(ll x =0; x < 2; ++x){
				if(a[i][j] < a[i - 1][x]) continue;
				dp1[i - 1][x] = max(dp1[i - 1][x], dp1[i][j] + x);
				dp2[i - 1][x] = min(dp2[i - 1][x], dp2[i][j] + x);
			}
		}
	}
	ll cur = 0;
	a[0][0] = 0;
	ll lft = n;
	for(ll i = 1; i <= 2 * n; ++i){
		if(a[i][0] >= a[i - 1][cur]){
			if(dp1[i][0] >= lft and dp2[i][0] <= lft){
				cout << 'A';
				cur = 0;
				continue;
			}
		}
		if(a[i][1] >= a[i - 1][cur]){
			if(dp1[i][1] >= lft and dp2[i][1] <= lft){
				cout << 'B';
				cur = 1;
				lft--;
				continue;
			}
		}
		cout << -1;
		return;
	}
}

int main(){
	// freopen("fairphoto.in", "r", stdin); freopen("fairphoto.out", "w", stdout);
	Magic
	// tsts{
		solve();
		cout << endl;
	// }
}

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