Submission #1229994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229994		Ghulam_Junaid	parentrises (BOI18_parentrises)	C++20	6 / 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 (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 output[21] = {0, 0, 1, 2, 2, 6, 12, 18, 43, 86, 148, 326, 652, 1194, 2531, 5062, 9578, 19884, 39768, 76680, 157236};

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

    int t;
    cin >> t >> t;
    while (t--){
        int n;
        cin >> n;
        cout << output[n] << endl;
    }
}

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