Submission #1259782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259782		son2008	Building 4 (JOI20_building4)	C++20	100 / 100	148 ms	28952 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define fi first
#define se second
// #define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int, ii>
#define iiii pair<ii, ii>
#define base 29
#define eps 1e-8
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
int dx[] = {0LL, 0LL, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0LL, 0LL, 1, -1, 1, -1};
const int maxn = 1e6 + 5, inf = 1e9;
const int mod = 1e9 + 7;
ii dp[maxn][2];
int a[maxn][2], n;
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#define task "task"
    if (fopen(task ".inp", "r"))
    {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    cin >> n;
    for (int j = 0; j < 2; j++)
    {
        for (int i = 1; i <= 2 * n; i++)
        {
            cin >> a[i][j];
        }
    }
    a[0][0] = a[0][1] = -inf;
    for (int i = 1; i <= 2 * n; i++)
    {
        dp[i][0] = dp[i][1] = mp(inf, -inf);
        for (int trc = 0; trc <= 1; trc++)
        {
            for (int cur = 0; cur <= 1; cur++)
            {
                if (a[i - 1][trc] <= a[i][cur])
                {
                //    cout << i << " " << trc << " " << cur << '\n';
                    dp[i][cur].fi = min(dp[i][cur].fi, dp[i - 1][trc].fi + (1 - cur));
                    dp[i][cur].se = max(dp[i][cur].se, dp[i - 1][trc].se + (1 - cur));
                }
            }
        }
    }
    int ok = -1;
    for (int tt = 0; tt <= 1; tt++)
    {
        if (dp[2 * n][tt].fi <= n && dp[2 * n][tt].se >= n)
        {
            ok = tt;
            break;
        }
    }
    if (ok == -1)
    {
        cout << -1;
        return 0;
    }
    vector<int> vec;
    int cnt = n;
    for (int i = 2 * n; i >= 1; i--)
    {
        int x = (ok ? a[i][1] : a[i][0]);
        vec.push_back(ok);
        cnt -= (1 - ok);
       // cout << cnt << " " << x << '\n';
        if (a[i - 1][1] <= x && dp[i - 1][1].fi <= cnt && dp[i - 1][1].se >= cnt)
            ok = 1;
        else
            ok = 0;
    }
    reverse(vec.begin(), vec.end());
    for (int x : vec)
    {
        cout << (x ? 'B' : 'A');
    }
    cerr << endl
         << "TIME : " << clock() * 0.001 << "s" << endl;
}

Compilation message (stderr)

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

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