Submission #1013106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013106		caterpillow	parentrises (BOI18_parentrises)	C++17	100 / 100	86 ms	23936 KiB

parentrises

#include <bits/stdc++.h>

using namespace std;

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;

ostream& operator<<(ostream& os, string o) {
    for (char c : o) os << c;
    return os;
}

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

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

*/

const ll mod = 1e9 + 7;

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

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

ll solve2() {
    ll n; cin >> n;
    vt<vt<ll>> dp(n + 1, vt<ll>(n + 1));
    auto rdp = dp;
    dp[0][0] = 1;
    F0R (i, n) {
        F0R (j, n) {
            // assign open
            add(dp[i + 1][j + 1], dp[i][j]);
            // assign closed
            ll cur_closed = i - j;
            if (2 * j - (cur_closed + 1) >= 0) {
                add(dp[i + 1][j], dp[i][j]);
            } 
        }
    }
    rdp[n][0] = 1;
    ROF (i, 1, n + 1) {
        F0R (j, n) {
            // assign closed
            add(rdp[i - 1][j + 1], rdp[i][j]);
            // assign open
            ll cur_open = n - i - j;
            if (2 * j - (cur_open + 1) >= 0) {
                add(rdp[i - 1][j], rdp[i][j]);
            }
        }   
    }
    ll ans = 0;
    F0R (i, n + 1) {
        F0R (j, i + 1) {
            ll cur_offset = 2 * j - (i - j);
            ll rem = n - i;
            ll req_closed = cur_offset + rem;
            if (req_closed % 3 != 0 || req_closed < 0) continue;
            req_closed /= 3;
            if (req_closed > n) continue;
            add(ans, (dp[i][j] * rdp[i][req_closed]) % mod);
        }
    }
    return ans;
}

string 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));
            out += rout;
            return out;
        }
    }
    return "impossible";
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int p, t; cin >> p >> t;
    if (p == 1) {
        F0R (i, t) cout << solve1() << endl;
    } else if (p == 2) {
        F0R (i, t) cout << solve2() << endl;
    }
}

Compilation message (stderr)

parentrises.cpp:183:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  183 | 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