Submission #1013717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013717		caterpillow	parentrises (BOI18_parentrises)	C++17	100 / 100	27 ms	24064 KiB

parentrises

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

/*

P = 1:
    "greedily open" some prefix
    and then "greedily close" some suffix

    if at some point there is a valid "turning point", then we can colour
    assign a first

P = 2:
    some sequence is rgb-readable if and only if there exists a greedy prefix + suffix of assignments
    there cannot be two greedy prefix/suffix assignments since it would throw off the balance

    compute # of greedy assignments for each prefix and each suffix

    dp[i][j] = # of ways to greedy assign first i parenthesis such that there are j open parenthesis
    rdp[i][j] # of ways to greedy assign the 1-indexed suffix such that there are j closed parenthesis
        which is the same thing but just backwards

*/

const ll mod = 1e9 + 7;

void add(ll& a, ll b) {
    a += b;
    a -= (a >= mod) * mod;
}

const ll bruh[2] = {1, -1};

void solve2() {
    const ll n = 300;
    vt<vt<ll>> dp(n + 1, vt<ll>(n + 1));
    dp[0][0] = 1;
    F0R (i, n) {
        F0R (j, n) {
            add(dp[i + 1][j + 1], dp[i][j]);
            if (3 * j - i - 1 >= 0) add(dp[i + 1][j], dp[i][j]);
        }
    }
    int t; cin >> t;
    F0R (_, t) {
        int m; cin >> m;
        ll ans = 0;
        F0R (i, m + 1) {
            F0R (j, i + 1) {
                ll req_closed = 3 * j - 2 * i + m;
                if (req_closed % 3 != 0 || req_closed < 0 || req_closed > 3 * m) continue;
                add(ans, (dp[i][j] * dp[m - i][req_closed / 3]) % mod);
            }
        }
        cout << ans << endl;
    }
}

void solve1() {
    string st; cin >> st;
    int n = size(st);
    vt<int> seq(n);
    F0R (i, n) seq[i] = st[i] == '(' ? 1 : -1;
    vt<pi> pfx(n + 1), sfx(n + 1);
    F0R (i, n) {
        pi prv = pfx[i];
        if (seq[i] == 1) prv.f++, prv.s++;
        else {
            if (prv.f == prv.s) prv.f--;
            else prv.s--;
        }
        if (prv.f < 0 || prv.s < 0) prv = {-inf, -inf};
        pfx[i + 1] = prv;
    }
    ROF (i, 0, n) {
        pi prv = sfx[i + 1];
        if (seq[i] == -1) prv.f++, prv.s++; 
        else {
            if (prv.f == prv.s) prv.f--;
            else prv.s--;
        }
        if (prv.f < 0 || prv.s < 0) prv = {inf, inf};
        sfx[i] = prv;
    }
    F0R (i, n + 1) {
        if (pfx[i].f == sfx[i].f && pfx[i].s == sfx[i].s) {
            // answer
            string out = "";
            string rout = "";
            int x = 0, y = 0;
            F0R (j, i) {
                if (seq[j] == 1) {
                    x++, y++;
                    out += 'G';
                } else {
                    if (x == y) out += 'R', x--;
                    else out += 'B', y--;
                }
            }
            x = y = 0;
            ROF (j, i, n) {
                if (seq[j] == -1) {
                    x--, y--;
                    rout += 'G';
                } else {
                    if (x == y) rout += 'R', x++;
                    else rout += 'B', y++;
                }
            }
            reverse(all(rout));
            cout << out << rout << endl;
            return;
        }
    }
    cout << "impossible" << endl;
}

main() {
    cin.tie(0)->sync_with_stdio(0);

    int p; cin >> p;
    if (p == 1) {
        int t; cin >> t;
        F0R (i, t) solve1();
    } else {
        solve2();
    }
}

Compilation message (stderr)

parentrises.cpp:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  138 | main() {
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28