Submission #1333097

#TimeUsernameProblemLanguageResultExecution timeMemory
1333097finalpoiBuilding 4 (JOI20_building4)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
template <typename T> using vec=vector<T>;

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;

int c[2*MAX_N][2];
bool l[2*MAX_N][2];
bool r[2*MAX_N][2];
int licz[4];

int mask(int i) {
    return ((l[i][0] && r[i][0])<<1 | (l[i][1] && r[i][1]));
}

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) {
        l[1][j]=1;
        r[2*N][j]=1;
    }
    for(int i=2; i<=2*N; ++i) {
        rep(j, 2) {
            rep(k, 2) {
                l[i][j]|=(l[i-1][k] && c[i-1][k]<=c[i][j]);
            }
        }
    }
    for(int i=2*N-1; i>=1; --i) {
        rep(j, 2) {
            rep(k, 2) {
                r[i][j]|=(r[i+1][k] && c[i][j]<=c[i+1][k]);
            }
        }
    }
    for(int i=1; i<=2*N; ++i) {
        ++licz[mask(i)];
    }
    bool ok=(min(licz[1], licz[2])+licz[3] >= N);
    if(licz[0]>0 || !ok) {
        cout<<(-1)<<nl;
    } else {
        int ile=0;
        for(int i=1; i<=2*N; ++i) {
            int m=mask(i);
            if(m==1 || (m==3 && ile<(N-licz[1]))) {
                if(m==3) { ++ile; }
                cout<<'B';
            } else {
                cout<<'A';
            }
        }
        cout<<nl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...