Submission #91029

#	Time	Username	Problem	Language	Result	Execution time	Memory
91029		choikiwon	parentrises (BOI18_parentrises)	C++17	100 / 100	267 ms	145232 KiB

parentrises

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

const int mod = 1e9 + 7;

string S, ans;

void main2() {
    cin >> S;

    int cnt = 0, open = 0;
    int mx1 = 0;
    int mx2 = 0;
    for(int i = 0; i < S.size(); i++) {
        if(S[i] == '(') cnt++, open++;
        else cnt--;
        mx1 = max(mx1, -cnt);
        if(-cnt > open) {
            cout << "impossible\n";
            return;
        }
    }
    cnt = open = 0;
    for(int i = (int)S.size() - 1; i >= 0; i--) {
        if(S[i] == ')') cnt++, open++;
        else cnt--;
        mx2 = max(mx2, -cnt);
        if(-cnt > open) {
            cout << "impossible\n";
            return;
        }
    }

    ans.clear();
    ans.resize(S.size());
    for(int i = 0; i < S.size(); i++) {
        if(mx1 && S[i] == '(') ans[i] = 'G', mx1--;
    }
    for(int i = (int)S.size() - 1; i >= 0; i--) {
        if(mx2 && S[i] == ')') ans[i] = 'G', mx2--;
    }

    int rg = 0;
    int bg = 0;
    for(int i = 0; i < S.size(); i++) {
        if(ans[i] == 'G') {
            if(S[i] == '(') rg++, bg++;
            else rg--, bg--;
        }
        else {
           if(S[i] == '(') {
                if(rg < bg) ans[i] = 'R', rg++;
                else ans[i] = 'B', bg++;
            }
            else {
                if(rg < bg) ans[i] = 'B', bg--;
                else ans[i] = 'R', rg--;
            }
        }
    }

    cout << ans << endl;
}

int cc[333][333][333];
int dp(int n, int open, int close) {
    int &ret = cc[n][open][close];
    if(ret != -1) return ret;
    if(n == 0) return ret = close == 0;

    ret = 0;
    ret += dp(n - 1, open + 2, close + 1);
    ret %= mod;
    if(open) {
        ret += dp(n - 1, open - 1, max(0, close - 2));
        ret %= mod;
    }
    return ret;
}

void main3() {
    int n; cin >> n;
    cout << dp(n, 0, 0) << endl;
}

int P, TC;
int main() {
    std::ios::sync_with_stdio(false);

    cin >> P >> TC;
    if(P == 1) {
        while(TC--) main2();
    }
    if(P == 2) {
        memset(cc, -1, sizeof(cc));
        while(TC--) main3();
    }
}

Compilation message (stderr)

parentrises.cpp: In function 'void main2()':
parentrises.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~
parentrises.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~
parentrises.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < S.size(); i++) {
                    ~~^~~~~~~~~~

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