Submission #1173605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173605		CrabCNH	Building 4 (JOI20_building4)	C++20	0 / 100	127 ms	251620 KiB

building4

#include <bits/stdc++.h>

#define task   "BriantheCrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())

using namespace std;

template <class T> void mini (T &t, T f) {if (t > f) t = f;}
template <class T> void maxi (T &t, T f) {if (t < f) t = f;}

const int maxN = 4e3 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

int a[maxN], b[maxN];
int dp[2][maxN / 2][2];
pii trace[maxN][maxN / 2][2];

void solve () {
    int n;
    cin >> n;
    for (int i = 1; i <= 2 * n; i ++) {
        cin >> a[i];
    }
    for (int i = 1; i <= 2 * n; i ++) {
        cin >> b[i];
    }
    for (int i = 1; i <= 2 * n; i ++) {
        dp[0][i][0] = dp[1][i][0] = dp[1][i][0] = dp[1][i][1] = 0; 
    }
    memset (trace, -1, szf (trace));
    dp[1][0][0] = dp[1][1][1] = 1;
    for (int i = 2; i <= 2 * n; i ++) {
        int cur = i & 1;
        int prev = 1 - cur;
        for (int curA = 0; curA <= n; curA ++) {
            dp[cur][curA][0] = dp[cur][curA][1] = 0;
            if (a[i] >= a[i - 1] && curA - 1 >= 0) {
                if (dp[prev][curA - 1][1]) {
                    dp[cur][curA][1] = 1;
                    trace[i][curA][1] = {curA - 1, 1};
                }
            }
            if (a[i] >= b[i - 1] && curA - 1 >= 0) {
                if (dp[prev][curA - 1][0]) {
                    dp[cur][curA][1] = 1;
                    trace[i][curA][1] = {curA - 1, 0};
                }
            }
            if (b[i] >= a[i - 1] && dp[prev][curA][1]) {
                dp[cur][curA][0] = 1;
                trace[i][curA][0] = {curA, 1};
            }
            if (b[i] >= b[i - 1] && dp[prev][curA][0]) {
                dp[cur][curA][0] = 1;
                trace[i][curA][0] = {curA, 0};
            }
            //cout << i << ' ' << curA << ' ' << dp[cur][curA][0] << ' ' << dp[cur][curA][1] << '\n';
        }
    }
    int nT = (2 * n), aT = n;
    bool tT;
    //cout << max (dp[(2 * n) & 1][n][0], dp[(2 * n) & 1][n][1]);
    if (dp[(2 * n) & 1][n][0] == 1) {
        tT = 0;
    }
    else if (dp[(2 * n) & 1][n][1] == 1){
        tT = 1;
    }
    else {
        cout << -1;
        return;
    }
    string res = "";
    //cout << trace[nT][aT][tT].fi << '\n';
    while (nT >= 1) {
        //cout << nT << ' ' << aT << ' ' << tT << '\n';
        res += (tT ? "A" : "B");  
        auto [aTT, tTT] = trace[nT][aT][tT];
        nT = nT - 1;
        aT = aTT;
        tT = tTT;
    }
    reverse (res.begin (), res.end ());
    cout << res;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfdgb

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:97:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building4.cpp:98:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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