Submission #1216393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216393		Malix	Building 4 (JOI20_building4)	C++20	100 / 100	176 ms	65192 KiB

building4

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int main() {   
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;cin>>n;
    int m=2*n;
    vi a(m),b(m);
    REP(i,0,m)cin>>a[i];
    REP(i,0,m)cin>>b[i];
    vector<vector<pi>> dp(m,vector<pi>(2,{inf,-inf}));
    dp[0]={{1,1},{0,0}};
    REP(i,1,m){
        if(a[i-1]<=a[i])dp[i][0]={min(dp[i][0].F,dp[i-1][0].F+1),max(dp[i][0].S,dp[i-1][0].S+1)};
        if(a[i-1]<=b[i])dp[i][1]={min(dp[i][1].F,dp[i-1][0].F),max(dp[i][1].S,dp[i-1][0].S)};
        if(b[i-1]<=a[i])dp[i][0]={min(dp[i][0].F,dp[i-1][1].F+1),max(dp[i][0].S,dp[i-1][1].S+1)};
        if(b[i-1]<=b[i])dp[i][1]={min(dp[i][1].F,dp[i-1][1].F),max(dp[i][1].S,dp[i-1][1].S)};
    }
    string ans;
    if((dp[m-1][0].F<=n&&n<=dp[m-1][0].S)||(dp[m-1][1].F<=n&&n<=dp[m-1][1].S)){
        int val;
        if(dp[m-1][0].F<=n&&n<=dp[m-1][0].S){
            ans.PB('A');
            n--;
            val=a.back();
        }
        else{
            ans.PB('B');
            val=b.back();
        }
        for(int i=m-2;i>=0;i--){
            if(dp[i][0].F<=n&&n<=dp[i][0].S&&a[i]<=val){
                ans.PB('A');
                n--;
                val=a[i];
            }
            else{
                ans.PB('B');
                val=b[i];
            }
        }
    }
    else{
        cout<<-1;
        return 0;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
}

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