Submission #1229981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229981		Ghulam_Junaid	parentrises (BOI18_parentrises)	C++20	50 / 100	27 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));
}

string get(string &s){
    string ans;
    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";
    return ans;
}

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

    int t;
    cin >> t >> t;
    while (t--){
        string s;
        cin >> s;
        cout << get(s) << '\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