Submission #217003

#	Time	Username	Problem	Language	Result	Execution time	Memory
217003		mhy908	Building 4 (JOI20_building4)	C++14	100 / 100	427 ms	26748 KiB

building4

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf=2000000000;
int n, a[1000010], b[1000010];
int dpsa[1000010], dpea[1000010], dpsb[1000010], dpeb[1000010];
char ans[1000010];
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n*2; i++)scanf("%d", &a[i]);
    for(int i=1; i<=n*2; i++)scanf("%d", &b[i]);
    for(int i=1; i<=n*2; i++){
        dpsa[i]=dpsb[i]=inf;
        dpea[i]=dpeb[i]=-inf;
        if(a[i-1]<=a[i]){
            dpsa[i]=min(dpsa[i], dpsa[i-1]+1);
            dpea[i]=max(dpea[i], dpea[i-1]+1);
        }
        if(b[i-1]<=a[i]){
            dpsa[i]=min(dpsa[i], dpsb[i-1]+1);
            dpea[i]=max(dpea[i], dpeb[i-1]+1);
        }
        if(a[i-1]<=b[i]){
            dpsb[i]=min(dpsb[i], dpsa[i-1]);
            dpeb[i]=max(dpeb[i], dpea[i-1]);
        }
        if(b[i-1]<=b[i]){
            dpsb[i]=min(dpsb[i], dpsb[i-1]);
            dpeb[i]=max(dpeb[i], dpeb[i-1]);
        }
    }
    if((dpsa[2*n]>n||dpea[2*n]<n)&&(dpsb[2*n]>n||dpeb[2*n]<n))return !printf("-1");
    int anum=n, bnum=n;
    for(int i=2*n; i>=1; i--){
        if(anum&&dpsa[i]<=anum&&dpea[i]>=anum&&((ans[i+1]=='A'&&a[i]<=a[i+1])||(ans[i+1]=='B'&&a[i]<=b[i+1])||i==2*n)){
            anum--;
            ans[i]='A';
        }
        else{
            assert(bnum>0);
            bnum--;
            ans[i]='B';
        }
    }
    printf("%s", ans+1);
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building4.cpp:10:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=n*2; i++)scanf("%d", &a[i]);
                              ~~~~~^~~~~~~~~~~~~
building4.cpp:11:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=n*2; i++)scanf("%d", &b[i]);
                              ~~~~~^~~~~~~~~~~~~

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