Submission #381498

#	Time	Username	Problem	Language	Result	Execution time	Memory
381498		KULIKOLD	Building 4 (JOI20_building4)	C++17	100 / 100	313 ms	75756 KiB

building4

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define x1 fdgfdgf
#define y1 fdhfdgfdg
#define endl '\n'
const ll DIM = 1E6+7;
const ll INF = 1E18;
ll A[DIM],B[DIM],ans[DIM];
pair<ll,ll> dp[2][DIM];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    n*=2;
    ll last = 0;
    for(ll i = 1;i<=n;++i) {
        cin>>A[i];
    }
    for(ll i = 1;i<=n;++i){
        cin>>B[i];
    }
    for(ll i = 1;i<=n;++i){
        dp[0][i] = dp[1][i] = {INF,-INF};
        if (A[i]>=A[i-1]){
            dp[0][i].first = min(dp[0][i].first,dp[0][i-1].first+1);
            dp[0][i].second = max(dp[0][i].second,dp[0][i-1].second+1);
        }
        if (A[i]>=B[i-1]){
            dp[0][i].first = min(dp[0][i].first,dp[1][i-1].first+1);
            dp[0][i].second = max(dp[0][i].second,dp[1][i-1].second+1);
        }
        if (B[i]>=A[i-1]){
            dp[1][i].first = min(dp[1][i].first,dp[0][i-1].first);
            dp[1][i].second = max(dp[1][i].second,dp[0][i-1].second);
        }
        if (B[i]>=B[i-1]){
            dp[1][i].first = min(dp[1][i].first,dp[1][i-1].first);
            dp[1][i].second = max(dp[1][i].second,dp[1][i-1].second);
        }
    }
    ll got = n/2;
    pair<ll,ll> cur;
    if (dp[0][n].first<=n/2 && n/2<=dp[0][n].second){
        cur = {0,n};
        got--;
        ans[n] = 0;
    }
    else if (dp[1][n].first<=n/2 && n/2<=dp[1][n].second){
        cur = {1,n};
        ans[n] = 1;
    }
    else{
        cout<<"-1\n";
        return 0;
    }
    while(cur.second>1){
        ll val;
        if (cur.first==0)val = A[cur.second];
        else val = B[cur.second];
        if (dp[0][cur.second-1].first<=got && got<=dp[0][cur.second-1].second && A[cur.second-1]<=val){
            --got;
            ans[cur.second-1] = 0;
            cur = {0,cur.second-1};
        }
        else{
            ans[cur.second-1] = 1;
            cur = {1,cur.second-1};
        }
    }
    for(ll i = 1;i<=n;++i){
        if (ans[i]==0)cout<<'A';
        else cout<<'B';
    }
    cout<<endl;
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:18:8: warning: unused variable 'last' [-Wunused-variable]
   18 |     ll last = 0;
      |        ^~~~

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