제출 #1036685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036685		underwaterkillerwhale	건물 4 (JOI20_building4)	C++17	0 / 100	1 ms	600 KiB

building4

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 1e6 + 7;
const int Mod = 1e9 + 7;
const int szBL = 240;
const int INF = 1e9 + 7;
const int BASE = 137;

int n, m;
int a[2][N];
pair<int,int> f[2][N]; ///nó có thể lấy tối đa đcn

void solution (){
    cin >> n;
//    n = 20;
    rep (i, 1, 2 * n) {
        cin >> a[0][i];
//        a[0][i]= i;
//        cout << a[0][i] << " ";
    }
    rep (i, 1, 2 * n) {
        cin >> a[1][i];
//        a[1][i]= Rand(a[0][i], a[0][i]);
    }
//    cout<<"\n";
//    return;
    f[0][1] = {1, 1};
    f[1][1] = {0, 0};
    rep (i, 2, 2 * n)
    rep (k, 0, 1) f[k][i] = {INF, -INF};
    rep (i, 1, 2 * n - 1) {
        rep (k, 0, 1) {
//            cout << i <<","<<k<<" "<<f[k][i].fs<<","<<f[k][i].se<<"\n";
            rep (t, 0, 1) {
                if (t == 0 && a[k][i] <= a[t][i + 1]) {
                    f[t][i + 1].fs = min(f[t][i + 1].fs, f[k][i].fs + 1);
                    f[t][i + 1].se = max(f[t][i + 1].se, f[k][i].se + 1);
                }
                else if (t == 1 && a[k][i] <= a[t][i + 1]) {
                    f[t][i + 1].fs = min(f[t][i + 1].fs, f[k][i].fs);
                    f[t][i + 1].se = max(f[t][i + 1].se, f[k][i].se);
                }
            }
        }
    }
//    cout << f[0][2 * n].fs <<","<<f[0][2 * n].se<<" "<<f[1][2 * n].fs<<","<<f[1][2 * n].se <<"\n";
    pair<int,int> u = {-1, -1};
    if (f[0][2 * n].se == n) u = {0, 2 * n};
    if (f[1][2 * n].se == n) u = {1, 2 * n};
    if (u.fs == -1) {
        cout << -1 <<"\n";
        return;
    }
    vector<int> vec;
    int num0 = n;
    while (u.se != 0) {
        vec.push_back(u.fs);
//        cout << u.fs<<" "<<u.se <<"\n";
        if (u.fs == 0) --num0;
        rep (k, 0, 1) {
            if (a[k][u.se - 1] <= a[u.fs][u.se] && f[k][u.se - 1].fs <= num0 && f[k][u.se - 1].se >= num0) {
                u = {k, u.se - 1};
                break;
            }
        }
    }
    reverse(ALL(vec));
    assert(num0 == 0);
    iter (&id, vec) {
        if (id == 0) cout <<"A";
        else cout <<"B";
    }
    cout<<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);
/*
*/
int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
no bug challenge +2
1,0 1,1
1,1 0,0
2,0 1,1
2,1 0,0
3,0 1,2
3,1 0,1
4,0 1,2
4,1 0,1
5,0 1,2
5,1 1000000007,-1000000007
6,0 2,3
6,1 1,2
7,0 0,3
7,1 0,2
8,0 0,4
8,1 0,2
9,0 0,3
9,1 0,4
10,0 0,5
10,1 0,3
11,0 0,4
11,1 0,5
0,6 0,5
*/

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