Submission #574929

#	Time	Username	Problem	Language	Result	Execution time	Memory
574929		snokes	Building 4 (JOI20_building4)	C++17	100 / 100	362 ms	137852 KiB

building4

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL

#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    vt<vt<int>> v(2, vt<int>(2 * N + 1));
    for(int i = 1; i <= 2 * N; i++) cin >> v[0][i];
    for(int i = 1; i <= 2 * N; i++) cin >> v[1][i];

    vt<vt<int>> mn(2 * N + 1, vt<int>(2, 1e9));
    vt<vt<int>> mx(2 * N + 1, vt<int>(2, -1e9));
    mn[0][0] = mn[0][1] = mx[0][0] = mx[0][1] = 0;

    for(int i = 1; i <= 2 * N; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                if(v[j][i] >= v[k][i - 1])
                {
                    mn[i][j] = min(mn[i][j], mn[i - 1][k] + j);
                    mx[i][j] = max(mx[i][j], mx[i - 1][k] + j);
                }
            }
        }
    }

    int idx = 0;
    while(idx < 2 && !(mn[2 * N][idx] <= N && N <= mx[2 * N][idx])) idx++;

    if(idx == 2)
    {
        cout << -1 << "\n";
        return 0;
    }

    string ans(2 * N, '?');
    for(int i = 2 * N, j = N; i > 0; i--)
    {
        ans[i - 1] = idx ? 'B' : 'A';
        j -= idx;
        int me = v[idx][i];
        if(me >= v[0][i - 1] && mn[i - 1][0] <= j && j <= mx[i - 1][0]) idx = 0;
        else idx = 1;
    }

    cout << ans << "\n";
}

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