Submission #257057

#	Time	Username	Problem	Language	Result	Execution time	Memory
257057		IsaacMoris	Building 4 (JOI20_building4)	C++14	100 / 100	445 ms	92444 KiB

building4

#include<iostream>
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N=1e6+3;
int n, dp1[N][2], dp2[N][2], a[N][2];
string ans="";
int solve1(int i, int prej)
{
    if(i==2*n+1)
        return 0 ;
    int &ans=dp1[i][prej];
    if(ans!=-1)
        return ans ;
    ans=20*n;
    if(a[i-1][prej]<=a[i][0])
        ans=1+min(ans,solve1(i+1,0));
    if(a[i-1][prej]<=a[i][1])
        ans=min(ans,solve1(i+1,1));
    return ans;
}
int solve2(int i, int prej)
{
    if(i==2*n+1)
        return 0 ;
    int &ans=dp2[i][prej];
    if(ans!=-1)
        return ans ;
    ans=-20*n;
    if(a[i-1][prej]<=a[i][0])
        ans=1+max(ans,solve2(i+1,0));
    if(a[i-1][prej]<=a[i][1])
        ans=max(ans,solve2(i+1,1));
    return ans;
}
void build(int i,int prej, int rem)
{
    if(i==2*n+1)
        return ;
    if(a[i-1][prej]<=a[i][0] && rem-1 >=solve1(i+1,0) && rem-1 <=solve2(i+1,0))
    {
        //cout<<0;
        ans+='A';
        build(i+1,0,rem-1);
        return ;
    }
    if(a[i-1][prej]<=a[i][1] && rem >=solve1(i+1,1) && rem <=solve2(i+1,1))
    {
        ans+='B';
       // cout<<1;
        build(i+1,1,rem);
        return ;
    }
}
int main()
{
    IO
    cin>>n;
    for(int j=0; j<2; j++)
        for(int i=1; i<=2*n; i++)
            cin>>a[i][j];
    memset(dp1,-1,sizeof dp1);
    memset(dp2,-1,sizeof dp2);
    build(1,0,n);
    if(ans.size()==2*n)
        cout<<ans;
    else
        cout<<-1;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ans.size()==2*n)
        ~~~~~~~~~~^~~~~

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