oj.uz

Submission #1013106

# Submission time Handle Problem Language Result Execution time Memory
1013106 2024-07-03T07:52:26 Z caterpillow parentrises (BOI18_parentrises) C++17
100 / 100
 86 ms 23936 KB 
#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

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

Subtask #2
11.0 / 11.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 452 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 4 ms 604 KB Output is correct
17 Correct 4 ms 2904 KB Output is correct
18 Correct 3 ms 820 KB Output is correct
19 Correct 3 ms 1564 KB Output is correct
20 Correct 5 ms 2904 KB Output is correct
21 Correct 32 ms 2136 KB Output is correct
22 Correct 41 ms 23936 KB Output is correct
23 Correct 29 ms 4524 KB Output is correct
24 Correct 33 ms 12432 KB Output is correct
25 Correct 39 ms 23924 KB Output is correct

Subtask #5
6.0 / 6.0

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

Subtask #6
16.0 / 16.0

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

Subtask #7
28.0 / 28.0

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