Submission #574900

#	Time	Username	Problem	Language	Result	Execution time	Memory
574900		snokes	Building 4 (JOI20_building4)	C++17	11 / 100	741 ms	524288 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<int> A(2 * N + 1), B(2 * N + 1);
    for(int i = 1; i <= 2 * N; i++) cin >> A[i];
    for(int i = 1; i <= 2 * N; i++) cin >> B[i];

    vt<vt<vt<bool>>> dp(N + 1, vt<vt<bool>>(N + 1, vt<bool>(2)));
    vt<vt<vt<tuple<int, int, int>>>> p(N + 1, vt<vt<tuple<int, int, int>>>(N + 1, vt<tuple<int, int, int>>(2, {-1, -1, -1})));
    dp[0][0][1] = dp[0][0][0] = true;
    for(int i = 0; i <= N; i++)
    {
        for(int j = 0; j <= N; j++)
        {
            if(i + j == 2 * N) continue;
            for(int k = 0; k < 2; k++)
            {
                if(!dp[i][j][k]) continue;
                int last = k ? B[j + i] : A[i + j];
                if(i < N && last <= A[j + i + 1])
                {
                    dp[i + 1][j][0] = true;
                    p[i + 1][j][0] = make_tuple(i, j, k);
                }
                if(j < N && last <= B[i + j + 1])
                {
                    dp[i][j + 1][1] = true;
                    p[i][j + 1][1] = make_tuple(i, j, k);
                }
            }
        }
    }

    //dbg(dp);

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

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

    string ans(2 * N, '?');
    for(int i = N, j = N; i > 0 || j > 0;)
    {
        ans[i + j - 1] = idx ? 'B' : 'A';
        tie(i, j, idx) = p[i][j][idx];
    }

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

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