Submission #1144524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144524		crafticat	parentrises (BOI18_parentrises)	C++20	72 / 100	1093 ms	13276 KiB

parentrises

#include <bits/stdc++.h>
using namespace std;

#define F0R(i,n) for(int i=0;i<n;i++)
#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--)

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;
const int INF=1e9+7;

using ll = long long;
const ll MOD = 1e9 + 7;

struct mint {
    ll v = 0;

    mint() = default;
    mint(ll x) : v(x % MOD) {
    }
    mint operator-(mint other) {
        return {v - other.v + MOD};
    }
    mint operator+(mint other) {
        return {v + other.v};
    }
    void operator+=(mint other) {
        v += other.v;
        v %= MOD;
    }
};

bool isBalanced(string s) {
    int n = s.length();
    int b = 0;

    for (auto c : s) {
        if (c == '(') {
            b++;
        } else if (c == ')') {
            b--;
            if (b < 0) return false;
        }
    }
    return b == 0;
}

int valid(int x, int t, int avoid) {
    if (t == avoid) return 0;
    return x;
}

int solveProblemB(int N) {
    int BOUNDS = N * 2;
    V<V<mint>> dp(V<V<mint>>(BOUNDS, V<mint>(BOUNDS, 0)));
    dp[0][0] = 1;

    FOR(i, 1, N + 1) {
        V<V<mint>> newDp(V<V<mint>>(BOUNDS, V<mint>(BOUNDS, 0)));
        FOR(j, 0, BOUNDS) {
            ROF(k, 0, BOUNDS) {
                int extra = -1;

                for (int dir = -2; dir <= 1; dir+=3) {
                    if (j + dir >= 0 and k + extra >= 0 and j + dir < BOUNDS and k + extra < BOUNDS)
                        newDp[j][k] += dp[j + dir][k + extra];
                }
                if (k > j) {
                    newDp[j][k - 1] += newDp[j][k];
                    newDp[j][k] = 0;
                }
            }
        }
        dp = newDp;
    }

    // 2, 4, 2 = 1
    // 2, 1, 1 = 1
    // 3, 0, 0 = 1

    mint ans = 0;
    F0R(i, BOUNDS) {
        FOR(k, 0, BOUNDS) {
            if (k != i) continue;
            ans += dp[i][k];
        }
    }
    return ans.v;
}

void solveProblemA() {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        vi colors(s.size(), 0);
        stack<int> st;
        stack<int> removers, last;
        bool possible = true;

        F0R(i,s.size()) {
            char c = s[i];
            if (c == '(') {
                st.push(i);
                last.push(i);
            }
            else if (c == ')') {
                if (st.empty()) {
                    removers.push(i);
                    if (removers.size() < 2) {
                        possible = false;
                        break;
                    } else {
                        colors[removers.top()] = 1; removers.pop();
                        colors[removers.top()] = 2; removers.pop();
                    }
                } else {
                    st.pop();
                    removers.push(i);
                }
            }
        }
        while (!st.empty() and last.size() >= 2) {
            int i = last.top(); last.pop();
            int j = last.top(); last.pop();
            colors[i] = 1; colors[j] = 2; st.pop();
        }
        if (!st.empty()) possible = false;
        string a, b;
        F0R(i,s.size()) {
            if (colors[i] == 0 or colors[i] == 1) {
                a.push_back(s[i]);
            }
            if (colors[i] == 0 or colors[i] == 2) {
                b.push_back(s[i]);
            }
        }
        if (!isBalanced(a) || !isBalanced(b)) possible = false;

        if (!possible) {
            cout << "impossible" << "\n";
            continue;
        }

        F0R(i, s.size()) {
            cout << (colors[i] == 0 ? "G" : colors[i] == 1 ? "B" : "R") << "";
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int p; cin >> p;
    if (p == 1) {
        solveProblemA();
    } else if (p == 2) {
        int t; cin >> t;
        while (t--) {
            int n; cin >> n;
            cout << solveProblemB(n) << "\n";
        }
    }

    return 0;
}

• 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: 0 / 28