Submission #1013897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013897		ReLice	Building 4 (JOI20_building4)	C++17	100 / 100	197 ms	68928 KiB

building4

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=1e6+7;
const ld eps=1e-9;
pair<ll,ll> dp[N][2];
void solve(){
    ll i,j;
    ll n;
    cin>>n;
    ll a[n*2+1],b[n*2+1];
    for(i=1;i<=n*2;i++)cin>>a[i];
    for(i=1;i<=n*2;i++)cin>>b[i];
    for(i=0;i<=n*2;i++){
        dp[i][0]=dp[i][1]={inf,-inf};
    }
    dp[1][0]={1,1};
    dp[1][1]={0,0};
    for(i=1;i<2*n;i++){
        if(a[i]<=a[i+1]){
            chmin(dp[i+1][0].fr,dp[i][0].fr+1);
            chmax(dp[i+1][0].sc,dp[i][0].sc+1);
        }
        if(b[i]<=a[i+1]){
            chmin(dp[i+1][0].fr,dp[i][1].fr+1);
            chmax(dp[i+1][0].sc,dp[i][1].sc+1);
        }
        if(a[i]<=b[i+1]){
            chmin(dp[i+1][1].fr,dp[i][0].fr);
            chmax(dp[i+1][1].sc,dp[i][0].sc);
        }
        if(b[i]<=b[i+1]){
            chmin(dp[i+1][1].fr,dp[i][1].fr);
            chmax(dp[i+1][1].sc,dp[i][1].sc);
        }
    }/*
    for(i=1;i<=n*2;i++){
        cout<<dp[i][0].fr<<' '<<dp[i][0].sc<<"  ";
    }cout<<endl;
    for(i=1;i<=n*2;i++){
        cout<<dp[i][1].fr<<' '<<dp[i][1].sc<<"  ";
    }cout<<endl;*/
    if((dp[n*2][0].fr>n || dp[n*2][0].sc<n) && (dp[2*n][1].fr>n || dp[2*n][1].sc<n)) { cout<<-1<<endl;return; }
    ll A=n,c,x=n*2;
    if(dp[n*2][0].fr>n || dp[n*2][0].sc<n) c=1;
    else c=0;
    str ans;
    while(x>1){
        x--;
        if(c==0){
            ans+='A';
            A--;
            if((dp[x][c].fr>A || dp[x][c].sc<A) || a[x]>a[x+1])c=1;
        }else{
            ans+='B';
            if((dp[x][c].fr>A || dp[x][c].sc<A) || b[x]>b[x+1]) c=0;
        }
    }
    if(A) ans+='A';
    else ans+='B';
    reverse(all(ans));
    cout<<ans<<endl;

}
signed main(){
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*
a<b<c<d
a a
b b

a a
a a



*/

Compilation message (stderr)

building4.cpp: In function 'void solve()':
building4.cpp:47:10: warning: unused variable 'j' [-Wunused-variable]
   47 |     ll i,j;
      |          ^

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