Submission #217002

#	Time	Username	Problem	Language	Result	Execution time	Memory
217002		mhy908	Building 4 (JOI20_building4)	C++14	100 / 100	420 ms	45304 KiB

building4

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n;
int 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]);
        }
        //printf("%d : %d ~ %d / %d ~ %d\n", i, dpsa[i], dpea[i], dpsb[i], dpeb[i]);
    }
    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:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building4.cpp:23: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:24: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