제출 #967169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967169		AlperenT_	건물 4 (JOI20_building4)	C++14	100 / 100	189 ms	69024 KiB

building4

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6+10 + 10,  inf = 1e9+10 , mod = 1e9 + 7 ;
pii dp[maxn][2]; 
int a[2][maxn];
string s ;
pii mrg(pii a, pii b){
    return {min(a.F,b.F) , max(a.S,b.S)};
}

void sl(int i ,int t ,int x){
    if(i==0)return ;
    if(t==1)x--;
    s += (t==1 ? "B" : "A") ;
    rep(j , 0 ,1){
        if(dp[i-1][j].F <= x && dp[i-1][j].S >= x && a[j][i-1] <= a[t][i]){
            sl(i-1, j , x) ;
            return ; 
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    int n;
    cin >> n ;
    rep(i ,1 , 2*n){
        cin >> a[0][i] ;
    }
    rep(i , 1, 2*n){
        cin >> a[1][i]; 
    }
    dp[1][0] = {0 , 0};
    dp[1][1] = {1, 1} ;
    rep(i , 2, 2*n){
        rep(j , 0 ,1){
            dp[i][j] ={inf,-inf}; 
            rep(k , 0 , 1){
                if(a[j][i] >= a[k][i-1]){
                    dp[i][j] = mrg(dp[i][j] , dp[i-1][k]) ;
                }
            }
        }
        dp[i][1].F++;
        dp[i][1].S++;
    }
    if(dp[2*n][0].F <=n && dp[2*n][0].S >= n){
        sl(2*n , 0 , n) ;
    }else if(dp[2*n][1].F <=n && dp[2*n][1].S >= n){
        sl(2*n , 1 , n);
    }else{
        cout << "-1\n";
        exit(0);
    }
    reverse(all(s)) ;
    cout << s << "\n"; 
    return 0 ;
}
/*


*/

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