Submission #623025

#	Time	Username	Problem	Language	Result	Execution time	Memory
623025		radal	Building 4 (JOI20_building4)	C++17	11 / 100	192 ms	31884 KiB

building4

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 4e3+10,mod = 998244353,inf = 1e9+10,sq = 700;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}
bool dp[N][N][2];
int a[N],b[N],n;
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    n *= 2;
    rep(i,0,n) cin >> a[i];
    rep(i,0,n) cin >> b[i];
    dp[n-1][1][0] = 1;
    dp[n-1][0][1] = 1;
    repr(i,n-2,0){
        rep(j,0,n){
            if (a[i+1] >= b[i]) dp[i][j][1] = dp[i+1][j][0];
            if (b[i+1] >= b[i]) dp[i][j][1] |= dp[i+1][j][1];
            if (j && a[i+1] >= a[i]) dp[i][j][0] = dp[i+1][j-1][0];
            if (j && b[i+1] >= a[i]) dp[i][j][0] |= dp[i+1][j-1][1];
        }
    }
    if (!(dp[0][n/2][0]|dp[0][n/2][1])){
        cout << -1 << endl;
        return 0;
    }
    int sd,cur = n/2;
    if (dp[0][n/2][0]) sd = 0;
    else sd = 1;
    rep(i,0,n){
        if (sd) cout << 'B';
        else cout << 'A';
        if (i+1 == n) return 0;
        if (sd){
            if (b[i+1] >= b[i] && dp[i+1][cur][1]){
                continue;
            }
            sd = 0;
            continue;
        }
        if (b[i+1] >= a[i] && dp[i+1][cur-1][1]){
            sd = 1;
            cur--;
            continue;
        }
        cur--;
    }
    return 0;
}

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