oj.uz

Submission #1013717

# Submission time Handle Problem Language Result Execution time Memory
1013717 2024-07-04T03:17:54 Z caterpillow parentrises (BOI18_parentrises) C++17
100 / 100
 27 ms 24064 KB 
#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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 3 ms 2908 KB Output is correct
18 Correct 2 ms 804 KB Output is correct
19 Correct 2 ms 1628 KB Output is correct
20 Correct 3 ms 2904 KB Output is correct
21 Correct 27 ms 2128 KB Output is correct
22 Correct 26 ms 23924 KB Output is correct
23 Correct 18 ms 4460 KB Output is correct
24 Correct 21 ms 12448 KB Output is correct
25 Correct 27 ms 24064 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 9 ms 1112 KB Output is correct