제출 #257057

#제출 시각아이디문제언어결과실행 시간메모리
257057IsaacMoris건물 4 (JOI20_building4)C++14
100 / 100
445 ms92444 KiB
#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;
}

컴파일 시 표준 에러 (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)
        ~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...