Submission #1229976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229976		Ghulam_Junaid	parentrises (BOI18_parentrises)	C++20	50 / 100	28 ms	7200 KiB

parentrises

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

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

bool check(string &s, string &ans){
    string a, b;
    for (int i = 0; i < s.size(); i ++){
        if (ans[i] == 'G'){
            a += s[i];
            b += s[i];
        }
        else if (ans[i] == 'B')
            b += s[i];
        else
            a += s[i];
    }
    return (RBS(a) and RBS(b));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t >> t;
    while (t--){
        string s, ans;
        cin >> s;
        int n = s.size();

        vector<int> vec;
        queue<int> q;
        for (int i = 0; i < n; i ++){
            ans += 'G';
            char c = s[i];
            if (c == '(')
                vec.push_back(i);
            else{
                if (vec.empty()){
                    if (q.empty()) continue;
                    int f = q.front();
                    q.pop();
                    ans[f] = 'R';
                    ans[i] = 'B';
                }
                else{
                    vec.pop_back();
                    q.push(i);
                }
            }
        }

        while (!q.empty()) q.pop();
        for (int i = n - 1; i >= 0; i --){
            if (vec.empty()) break;
            if (s[i] == ')') continue;
            int l = vec.back();
            if (l < i) q.push(i);
            else{
                vec.pop_back();
                if (q.empty()) continue;
                int f = q.front();
                q.pop();
                ans[f] = 'R';
                ans[i] = 'B';
            }
        }

        if (!check(s, ans))
            ans = "impossible";
        cout << ans << '\n';
    }
}

• 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