제출 #1271953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271953		Alebn	parentrises (BOI18_parentrises)	C++20	50 / 100	75 ms	20364 KiB

parentrises

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

signed main() {
    int t, p;
    cin >> p >> t;
    while(t--) {
        string s;
        cin >> s;
        int n = s.size(), sum = 0;
        string res(n, 'G');
        stack<int> l, r;
        bool ok = true;
        for(int i = 0; i < n; i++) {
            if(s[i] == '(') {
                sum++;
                l.push(i);
            } else {
                sum--;
                r.push(i);
            }
            if(sum < 0) {
                if(r.size() < 2) {
                    ok = false;
                    break;
                }
                res[r.top()] = 'R';
                r.pop();
                res[r.top()] = 'B';
                r.pop();
                sum++;
            }
        }
        while(sum--) {
            if(l.size() < 2) {
                ok = false;
                break;
            }
            res[l.top()] = 'R';
            l.pop();
            res[l.top()] = 'B';
            l.pop();
        }
        int a = 0, b = 0;
        for(int i = 0; i < n; i++) {
            sum = (s[i] == '(' ? 1 : -1);
            if(res[i] == 'R' || res[i] == 'G') a += sum;
            if(res[i] == 'B' || res[i] == 'G') b += sum;
            if(a < 0 || b < 0) ok = false;
        }
        if(a || b) ok = false;
        if(ok) cout << res << "\n";
        else cout << "impossible\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