Submission #223087

#	Time	Username	Problem	Language	Result	Execution time	Memory
223087		the_art_of_war	Building 4 (JOI20_building4)	C++17	0 / 100	5 ms	384 KiB

building4

//
// Created by Ильдар Ялалов on 14.01.2020.
//
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
typedef unsigned int uint;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define mp make_pair
#define all(a) a.begin(),a.end()

#ifdef zxc

#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

bool debug = 0;
const int MAXN = (1e6) + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (1e7 + 100);

int a[MAXN], b[MAXN];
pii dp[MAXN][2];

pii operator+(pii &a, int b) {
    if (a.fi < 0)
        return a;
    return {a.fi + b, a.se + b};
}

pii operator*(pii a, pii b) {
    if (a.fi == -1)
        return b;
    if (b.fi == -1)
        return a;
    return {min(a.fi, b.fi), max(a.se, b.se)};
}

bool in(pii a, int x) {
    return x >= a.fi && x <= a.se;
}

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];
    }

    dp[0][0] = {0, 0};
    dp[0][1] = {-1, -1};
    for (int i = 1; i <= 2 * n; ++i) {
        dp[i][0] = dp[i][1] = {-1, -1};
        if (a[i] > a[i - 1]) {
            dp[i][0] = dp[i - 1][0];
        }
        if (a[i] > b[i - 1]) {
            dp[i][0] = dp[i][0] * dp[i - 1][1];
        }
        dp[i][0] = dp[i][0] + 1;

        if (b[i] > a[i - 1]) {
            dp[i][1] = dp[i - 1][0];
        }
        if (b[i] > b[i - 1]) {
            dp[i][1] = (dp[i][1] * dp[i - 1][1]);
        }
        debug(i, dp[i][0], dp[i][1]);
    }
    debug(dp[2 * n][0], dp[2 * n][1]);


    int pos = -1;
    if (in(dp[2 * n][0], n)) {
        pos = 0;
    } else if (in(dp[2 * n][1], n)) {
        pos = 1;
    } else {
        cout << -1;
        return;
    }

    int have = n;
    string ans;
    for (int i = 2 * n; i >= 1; --i) {
        int val;
        if (pos == 0) {
            have--;
            val = a[i];
            ans.pb('A');
        } else {
            val = b[i];
            ans.pb('B');
        }
        if (val > a[i - 1] && in(dp[i - 1][0], have)) {
            pos = 0;
        } else {
            pos = 1;
        }
    }
    reverse(all(ans));
    cout << ans << "\n";
    return;


}

// CHECK LIMITS (n <= 10^5)
// CHECK CORNER CASES ( n==1)
signed main() {
#ifdef zxc
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#else
#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(15);


    int t = 1;
    while (t--) {
        solve();
    }
    debug(1.0 * clock() / CLOCKS_PER_SEC);
}

Compilation message (stderr)

building4.cpp: In function 'void solve()':
building4.cpp:92:37: warning: statement has no effect [-Wunused-value]
         debug(i, dp[i][0], dp[i][1]);
                                     ^
building4.cpp:94:38: warning: statement has no effect [-Wunused-value]
     debug(dp[2 * n][0], dp[2 * n][1]);
                                      ^
building4.cpp: In function 'int main()':
building4.cpp:151:42: warning: statement has no effect [-Wunused-value]
     debug(1.0 * clock() / CLOCKS_PER_SEC);
                                          ^

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