제출 #1229963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229963		Ghulam_Junaid	parentrises (BOI18_parentrises)	C++20	0 / 100	0 ms	328 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 1;
}

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) & RBS(b);
}

int main(){
    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] == ')' or ans[i] != 'G') continue;
            int l = vec.back();
            if (l < i) q.push(i);
            else{
                vec.pop_back();
                if (q.empty()) continue;
                int f = q.front();
                ans[f] = 'R';
                ans[i] = 'B';
            }
        }

        if (!check(s, ans))
            ans = "impossible";
        cout << ans << endl;
    }
}

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