Submission #300147

#	Time	Username	Problem	Language	Result	Execution time	Memory
300147		BeanZ	Building 4 (JOI20_building4)	C++14	100 / 100	407 ms	146168 KiB

building4

// I_LOVE_LPL
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int lim = 3e2;
ll inf = 1e18;
ll a[N][2], vis[N][2];
pair<ll, ll> dp[N][2]; // dem B
void DP(ll i, ll j){
        if (vis[i][j]) return;
        vis[i][j] = 1;
        ll mn = inf, mx = -inf;
        if (a[i][j] <= a[i + 1][0]){
                DP(i + 1, 0);
                mn = min(mn, dp[i + 1][0].first);
                mx = max(mx, dp[i + 1][0].second);
        }
        if (a[i][j] <= a[i + 1][1]){
                DP(i + 1, 1);
                mn = min(mn, dp[i + 1][1].first + 1);
                mx = max(mx, dp[i + 1][1].second + 1);
        }
        dp[i][j] = {mn, mx};
        //cout << dp[i][j].first << " " << dp[i][j].second << endl;
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.inp", "r")){
                freopen("test.inp", "r", stdin);
                freopen("test.out", "w", stdout);
        }
        ll n;
        cin >> n;
        n *= 2;
        for (int j = 0; j < 2; j++){
                for (int i = 1; i <= n; i++){
                        cin >> a[i][j];
                }
        }
        vis[n][0] = vis[n][1] = 1;
        DP(0, 0);
        if (dp[0][0].first > (n / 2) || dp[0][0].second < (n / 2)) return cout << -1, 0;
        ll cur = n / 2;
        ll last = 0;
        for (int i = 1; i <= n; i++){
                //cout << dp[i][1].first << " " << dp[i][1].second << endl;
                if (a[i][1] >= a[i - 1][last] && dp[i][1].first <= (cur - 1) && (cur - 1) <= dp[i][1].second){
                        cout << "B";
                        last = 1;
                        cur--;
                } else {
                        cout << "A";
                        last = 0;
                }
        }
}
/*
*/

Compilation message (stderr)

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

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