Submission #139206

#	Time	Username	Problem	Language	Result	Execution time	Memory
139206		mlyean00	parentrises (BOI18_parentrises)	C++17	50 / 100	69 ms	4740 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;

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;

            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;
                }
            }
            if (possible) {
                cout << ans;
            } else {
                cout << "impossible";
            }
            cout << endl;
        }
    } else if (p == 2) {
        assert(false);
    }

    return 0;
}

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