Submission #1193673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193673		Newtonabc	Building 4 (JOI20_building4)	C++20	100 / 100	512 ms	25992 KiB

building4

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
//dp[i][j]=keep range of possible a in the state that iterate from 1 to i and pick i at a/b (0/1)
pair<int,int> dp[N][2];
int a[N],b[N];
void upd(pair<int,int> &a,pair<int,int> b,int add){
    if(b.first==INT_MAX) add=0;
    a={min(a.first,b.first+add),max(a.second,b.second+add)};
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=2*n;i++) cin>>a[i];
    for(int i=1;i<=2*n;i++) cin>>b[i];
    for(int i=2;i<=2*n;i++) dp[i][0]=dp[i][1]={INT_MAX,INT_MIN};
    dp[1][0]={1,1},dp[1][1]={0,0};
    for(int i=2;i<=2*n;i++){
        if(a[i]>=a[i-1]) upd(dp[i][0],dp[i-1][0],1);
        if(a[i]>=b[i-1]) upd(dp[i][0],dp[i-1][1],1);
        if(b[i]>=a[i-1]) upd(dp[i][1],dp[i-1][0],0);
        if(b[i]>=b[i-1]) upd(dp[i][1],dp[i-1][1],0);
        //cout<<dp[i][0].first <<" " <<dp[i][0].second <<"," <<dp[i][1].first <<" " <<dp[i][1].second <<"\n";
    }
    int use=n,now=INT_MAX;
    vector<char> v;
    for(int i=2*n;i>=1;i--){
        if((dp[i][0].first<=use && use<=dp[i][0].second) && now>=a[i]){
            use--;
            now=a[i];
            v.push_back('A');
            //cout<<'a' <<" ";
        }
        else if((dp[i][1].first<=use && use<=dp[i][1].second) && now>=b[i]){
            v.push_back('B');
            now=b[i];
            //cout<<'b' <<" ";
        }
        else{
          if(i!=2*n){
            return 0;
          }
            cout<<-1;
            return 0;
        }
    }
    reverse(v.begin(),v.end());
    for(auto c:v){
        cout<<c;
    }
}

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