Submission #1333455

#TimeUsernameProblemLanguageResultExecution timeMemory
1333455finalpoiBuilding 4 (JOI20_building4)C++20
100 / 100
166 ms25840 KiB
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
template <typename T> using vec=vector<T>;
template <typename T> inline void ckmax(T& a, const T& b) { if(a<b) { a=b; } }
template <typename T> inline void ckmin(T& a, const T& b) { if(a>b) { a=b; } }

constexpr char nl='\n';
#define fi first
#define se second
#define pb push_back
#define cref const auto&
#define sz(c) (int)(c).size()
#define all(c) c.begin(),c.end()
#define rep(a, b) for(decltype(b) a=0; a<b; ++a)

#ifdef LOCAL
#define DEBUG 1
#else
#define DEBUG 0
#endif
#define ifbug if constexpr(DEBUG)
#define bug(...) ifbug{cerr<<"["#__VA_ARGS__"]: ";bug__(__VA_ARGS__);cerr<<'\n';}
template <typename...A> void bug__(A&&...a){((cerr<<a<<' '),...);}

struct DebugStream {
    template <typename T>
    constexpr DebugStream& operator<<(T&& value) const {
        ifbug std::cerr<<std::forward<T>(value);
        return const_cast<DebugStream&>(*this);
    }
};
inline constexpr DebugStream cbug{};

constexpr int MAX_N=5e5+6;
constexpr int INF=MAX_N;
constexpr int NEGINF=-MAX_N;

int c[2*MAX_N][2];
int dp_min[2*MAX_N][2];
int dp_max[2*MAX_N][2];

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin>>N;
    rep(j, 2) {
        for(int i=1; i<=2*N; ++i) {
            cin>>c[i][j];
        }
    }
    rep(j, 2) {
        dp_min[1][j]=j;
        dp_max[1][j]=j;
    }
    for(int i=2; i<=2*N; ++i) {
        rep(j, 2) {
            dp_min[i][j]=INF;
            dp_max[i][j]=NEGINF;
        }
        rep(j, 2) {
            rep(k, 2) {
                if(c[i-1][k] <= c[i][j]) {
                    ckmin(dp_min[i][j], dp_min[i-1][k]+(j));
                    ckmax(dp_max[i][j], dp_max[i-1][k]+(j));
                }
            }
        }
    }
    string wyn; wyn.reserve(2*N);
    int j=-1;
    rep(jj, 2) {
        if(dp_min[2*N][jj] <= N && N <= dp_max[2*N][jj]) {
            j=jj;
            break;
        }
    }
    if(j==-1) {
        cout<<(-1)<<nl;
        return 0;
    }
    int ile=N;
    for(int i=2*N; i>=1; --i) {
        wyn.pb((j==0 ?'A' :'B'));
        ile-=j;
        if(i==1) {
            break;
        }
        rep(k, 2) {
            if(c[i-1][k] <= c[i][j] && dp_min[i-1][k] <= ile && ile <= dp_max[i-1][k]) {
                j=k;
                break;
            }
        }
    }
    reverse(all(wyn));
    cout<<wyn<<nl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...