Submission #59744

#	Time	Username	Problem	Language	Result	Execution time	Memory
59744		model_code	parentrises (BOI18_parentrises)	C++17	100 / 100	276 ms	15348 KiB

parentrises

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const string IMPOSSIBLE = "impossible";
const int MOD = (int) 1e9 + 7;

enum Color {
    GREEN = 'G',
    RED = 'R',
    BLUE = 'B',
};

template<class F>
string filter(const string& s, const F& pred) {
    string ret;
    for (int i = 0; i < (int) s.length(); ++i) {
        if (pred(i, s[i])) {
            ret += s[i];
        }
    }
    return ret;
}

bool check(string s) {
    int balance = 0;
    for (char c: s) {
        if (c == '(') {
            balance++;
        } else {
            balance--;
            if (balance < 0) {
                return false;
            }
        }
    }
    return balance == 0;
}

string reconstruct(string s) {
    int n = (int) s.length();
    vector<Color> color(n, Color::GREEN);
    vector<int> greenOpen, greenClosed;
    int balance = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            greenOpen.push_back(i);
            balance++;
        } else {
            balance--;
            greenClosed.push_back(i);
            if (balance < 0) {
                balance = 0;
                if (greenClosed.size() < 2U) {
                    return IMPOSSIBLE;
                }
                int pos1 = greenClosed.back();
                greenClosed.pop_back();
                int pos2 = greenClosed.back();
                greenClosed.pop_back();
                color[pos1] = Color::RED;
                color[pos2] = Color::BLUE;
            }
        }
    }
    while (balance-- > 0) {
        if (greenOpen.size() < 2U) {
            return IMPOSSIBLE;
        }
        int pos1 = greenOpen.back();
        greenOpen.pop_back();
        int pos2 = greenOpen.back();
        greenOpen.pop_back();
        color[pos1] = Color::RED;
        color[pos2] = Color::BLUE;
    }
    string s1 = filter(s, [&color](int index, char c) -> bool {
        return color[index] == Color::RED || color[index] == Color::GREEN;
    });
    string s2 = filter(s, [&color](int index, char c) -> bool {
        return color[index] == Color::BLUE || color[index] == Color::GREEN;
    });
    string ans;
    for (int i = 0; i < n; ++i) {
        ans += (char) color[i];
    }
    return (check(s1) && check(s2)) ? ans: IMPOSSIBLE;
}

vector<int> count(int n) {
    vector<vector<int>> dp(n + 5, vector<int>(2 * n + 5, 0));
    auto ndp = dp;
    vector<int> ans(n + 1);
    ans[0] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (auto& v: ndp) {
            fill(v.begin(), v.end(), 0);
        }
        for (int left = 0; left <= n; ++left) {
            for (int right = left; right <= 2 * i; ++right) {
                ndp[left + 1][right + 2] += dp[left][right];
                ndp[left + 1][right + 2] %= MOD;
                int nLeft = max(0, left - 2);
                int nRight = right - 1;
                if (nLeft <= nRight) {
                    ndp[nLeft][nRight] += dp[left][right];
                    ndp[nLeft][nRight] %= MOD;
                }
            }
        }
        ndp.swap(dp);
        ans[i] = 0;
        for (int right = 0; right <= 2 * i; ++right) {
            ans[i] += dp[0][right];
            ans[i] %= MOD;
        }
    }
    return ans;
}

int main() {
    int type;
    cin >> type;

    if (type == 1) {
        int T;
        cin >> T;

        while (T-- > 0) {
            string s;
            cin >> s;
            cout << reconstruct(move(s)) << '\n';
        }
    } else {
        int T;
        cin >> T;

        vector<int> qs(T);
        for (int& x: qs) {
            cin >> x;
        }
        vector<int> ans = count(*max_element(qs.begin(), qs.end()));
        for (int x: qs) {
            cout << ans[x] << '\n';
        }
    }
}

• 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