Submission #1254637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254637		Alexe1900	parentrises (BOI18_parentrises)	C++20	50 / 100	65 ms	7480 KiB

parentrises

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

#define int long long

using vi = vector<int>;
using vvi = vector<vi>;

signed main() {
    int p; cin >> p;
    int t; cin >> t;

    while (t--) {
        if (p == 1) {
            string brackets; cin >> brackets;
            queue<int> q;
            string colors; colors.resize(brackets.length(), '?');
            int cnt = 0;
            int possible = 1;
            for (int i = 0; i < brackets.length(); i++) {
                if (brackets[i] == '(') {
                    q.push(i);
                    cnt++;
                } else {
                    if (cnt == 0) {
                        if (q.empty()) {
                            possible = 0;
                            break;
                        }
                        int a = q.front();
                        q.pop();
                        colors[a] = 'G';
                    } else cnt--;
                }
            }

            if (!possible) {
                cout << "impossible\n";
                continue;
            }

            for (int i = brackets.length()-1; i >= 0; i--) {
                if (brackets[i] == ')' and cnt) {
                    cnt--;
                    colors[i] = 'G';
                }
            }

            if (cnt > 0) {
                cout << "impossible\n";
                continue;
            }

            int sr = 0, sb = 0;

            for (int i = 0; i < brackets.length(); i++) {
                if (brackets[i] == '(') {
                    if (colors[i] != 'G') {
                        cnt++;
                        if (cnt % 2 == 0) colors[i] = 'R';
                        else colors[i] = 'B';
                    }
                    if (colors[i] != 'R') sb++;
                    if (colors[i] != 'B') sr++;
                } else {
                    if (colors[i] != 'G') {
                        if (cnt % 2 == 0) colors[i] = 'R';
                        else colors[i] = 'B';
                        cnt--;
                    }
                    if (colors[i] != 'R') sb--;
                    if (colors[i] != 'B') sr--;
                }
                if (sb < 0 or sr < 0) {
                    possible = 0;
                    break;
                }
            }

            if (!possible) {
                cout << "impossible\n";
                continue;
            }

            if (sb == 0 and sr == 0) cout << colors << "\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