Submission #1266883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266883		quangminh412	Building 4 (JOI20_building4)	C++17	0 / 100	1 ms	580 KiB

building4

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 1e6 + 1;

pair<int, int> dp[2][maxn];
int a[maxn], b[maxn];
int n;

void transit(pair<int, int> s, pair<int, int>& t, int offset)
{
    int l = s.first, r = s.second, u = t.first, v = t.second;
    l += offset; r += offset;
    r = min(r, n);
    if (u == -1)
        t = {l, r};
    else
        t = {min(l, u), max(r, v)};
}

bool include(pair<int, int> p, int x) { return (p.first <= x && x <= p.second); }

void solve()
{
    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] = dp[1][0] = {0, 0};
    for (int i = 1; i <= 2 * n; i++)
    {
        // use A
        dp[0][i] = {-1, -1};
        if (a[i - 1] <= a[i])
            transit(dp[0][i - 1], dp[0][i], 1);
        if (b[i - 1] <= a[i])
            transit(dp[1][i - 1], dp[0][i], 1);
        // use B
        dp[1][i] = {-1, -1};
        if (a[i - 1] <= b[i])
            transit(dp[0][i - 1], dp[1][i], 0);
        if (b[i - 1] <= b[i])
            transit(dp[1][i - 1], dp[1][i], 0);
    }

    int st = -1;
    if (include(dp[0][2 * n], n)) st = 0;
    if (include(dp[1][2 * n], n)) st = 1;
    if (st == -1)
    {
        cout << -1 << '\n';
        return;
    }

    int cur = n;
    vector<char> ans(2 * n + 1);
    for (int i = 2 * n; i > 0; i--)
    {
        ans[i] = (st == 0 ? 'A' : 'B');
        int x = (st == 0 ? a[i] : b[i]);
        if (st == 0)
            cur--;
        if (a[i - 1] <= x && include(dp[0][i - 1], cur))
            st = 0;
        if (b[i - 1] <= x && include(dp[1][i - 1], cur))
            st = 1;
    }

    for (int i = 1; i <= 2 * n; i++)
        cout << ans[i];
    cout << '\n';
}

Compilation message (stderr)

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

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