Submission #1266875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266875		quangminh412	Building 4 (JOI20_building4)	C++17	11 / 100	151 ms	63144 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 = 4000 + 1;

int a[maxn], b[maxn];
int dp[2][maxn][maxn];
int n;

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][0] = dp[1][0][0] = 1;
    for (int i = 1; i <= 2 * n; i++)
        for (int j = 0; j <= n; j++)
        {
            // use A this time
            if (a[i - 1] <= a[i] && j != 0)
                dp[0][j][i] |= dp[0][j - 1][i - 1];
            if (b[i - 1] <= a[i] && j != 0)
                dp[0][j][i] |= dp[1][j - 1][i - 1];
            // use B this time
            if (a[i - 1] <= b[i])
                dp[1][j][i] |= dp[0][j][i - 1];
            if (b[i - 1] <= b[i])
                dp[1][j][i] |= dp[1][j][i - 1];
        }

    int st = -1;
    if (dp[0][n][2 * n] == 1) st = 0;
    if (dp[1][n][2 * n] == 1) 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 && dp[0][cur][i - 1])
            st = 0;
        if (b[i - 1] <= x && dp[1][cur][i - 1])
            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: 11 / 11
• Subtask 2: 0 / 89