Submission #139216

#	Time	Username	Problem	Language	Result	Execution time	Memory
139216		mlyean00	parentrises (BOI18_parentrises)	C++17	56 / 100	1053 ms	4272 KiB

parentrises

#ifdef DEBUG
#include "debug.hpp"
#else
#pragma GCC optimize("Ofast")
#define trace(...)
#include <bits/stdc++.h>
#define endl '\n'
#endif

using namespace std;

const int MOD = 1'000'000'007;

string rgb_string(string const& s) {
    int n = s.length();
    vector<bool> red(n), blue(n);

    {
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                st.push(i);
            } else if (s[i] == ')') {
                if (!st.empty()) {
                    red[i] = true;
                    red[st.top()] = true;
                    st.pop();
                }
            }
        }
    }
    bool possible = true;
    {
        stack<int> st_red, st_blue;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                if (red[i]) {
                    st_red.push(i);
                } else {
                    st_blue.push(i);
                }
            } else if (s[i] == ')') {
                if (red[i]) {
                    if (!st_blue.empty()) {
                        blue[i] = true;
                        blue[st_blue.top()] = true;
                        st_blue.pop();
                    }
                } else {
                    if (st_red.empty())
                        possible = false;
                    else {
                        blue[i] = true;
                        blue[st_red.top()] = true;
                        st_red.pop();
                    }
                }
            }
            if (!possible) break;
        }
    }

    string ans;
    for (int i = 0; i < n; ++i) {
        if (red[i] && blue[i]) {
            ans.push_back('G');
        } else if (red[i]) {
            ans.push_back('R');
        } else if (blue[i]) {
            ans.push_back('B');
        } else {
            possible = false;
        }
    }
    return possible ? ans : "";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int p, t;
    cin >> p >> t;
    if (p == 1) {
        while (t--) {
            string s;
            cin >> s;

            string ans = rgb_string(s);
            cout << (ans.empty() ? "impossible" : ans) << endl;
        }
    } else if (p == 2) {
        while (t--) {
            int n;
            cin >> n;

            int ans = 0;
            for (int i = 0; i < 1 << n; ++i) {
                string s(n, '(');
                for (int j = 0; j < n; ++j) {
                    if ((i >> j) & 1) s[j] = ')';
                }
                if (!rgb_string(s).empty()) ++ans;
            }
            cout << ans << endl;
        }
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28