Submission #365530

#	Time	Username	Problem	Language	Result	Execution time	Memory
365530		lookcook	parentrises (BOI18_parentrises)	C++17	72 / 100	65 ms	4360 KiB

parentrises

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 1000005;
char res[maxn];
char s[maxn];
int n;

bool subtask1(bool type) {
    bool ok = true;
    bool turn = true;
    int sr = 0;
    int sb = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            res[i] = 'G';
            sr++;
            sb++;
        } else {
            if (turn) {
                res[i] = 'R';
                sr--;
            } else {
                res[i] = 'B';
                sb--;
            }
            turn = !turn;
        }
        if (sr < 0 || sb < 0) ok = false;
    }
    if (sb>sr) {
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == '(') {
                res[i] = 'R';
                break;
            }
            if (s[i] == ')' && res[i] == 'R') {
                res[i] = 'G';
                break;
            }
        }
    }
    sr = 0;
    sb = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == ')') {
            if (res[i] == 'G') {
                sr--;
                sb--;
            }
            if (res[i] == 'R') sr--;
            if (res[i] == 'B') sb--;
        } else {
            if (res[i] == 'G') {
                sr++;
                sb++;
            }
            if (res[i] == 'R') sr++;
            if (res[i] == 'B') sb++;
        }
        if (sr < 0 || sb < 0) ok = false;
    }
    for (int i =n-1; i >= 0; i--) {
        if (s[i] == '(' && res[i] == 'G') {
            if (sr>=sb && sr>0) { // maybe swap order?
                sr--;
                res[i] = 'B';
            } else if (sb > 0) {
                sb--;
                res[i] = 'R';
            }
        }
        if (s[i] == ')') {
            if (res[i] == 'R' && sb>0) {
                res[i] = 'G';
                sb--;
            } else if (res[i] == 'B' && sr>0) {
                res[i] = 'G';
                sr--;
            }
        }
    }
    sr = 0;
    sb = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == ')') {
            if (res[i] == 'G') {
                sr--;
                sb--;
            }
            if (res[i] == 'R') sr--;
            if (res[i] == 'B') sb--;
        } else {
            if (res[i] == 'G') {
                sr++;
                sb++;
            }
            if (res[i] == 'R') sr++;
            if (res[i] == 'B') sb++;
        }
        if (sr < 0 || sb < 0) ok = false;
    }
    if (type) {
        if (ok && sr == 0 && sb == 0) {
            for (int i = 0; i < n; i++) cout << res[i];
            cout << '\n';
        } else {
            cout << "impossible\n";
        }
    } else {
        return ok&&sr==0&&sb==0;
    }
    return false;
}

int dp[31];
void brute(int pos) {
    if (pos == n) {
        if (subtask1(false)) {
            dp[pos]++;
        }
        return;
    }
    s[pos] = '(';
    brute(pos+1);
    s[pos] = ')';
    brute(pos+1);
}

void lmao() {
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 2;
    dp[5] = 6;
    dp[6] = 12;
    dp[7] = 18;
    dp[8] = 43;
    dp[9] = 86;
    dp[10] = 148;
    dp[11] = 326;
    dp[12] = 652;
    dp[13] = 1194;
    dp[14] = 2531;
    dp[15] = 5062;
    dp[16] = 9578;
    dp[17] = 19884;
    dp[18] = 39768;
    dp[19] = 76680;
    dp[20] = 157236;
    dp[21] = 314472;
    dp[22] = 613440;
    dp[23] = 1248198;
    dp[24] = 2496396;
    dp[25] = 4906266;
    dp[26] = 9932707;
    dp[27] = 19865414;
    dp[28] = 39237478;
    dp[29] = 79165646;
    dp[30] = 158331292;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int p, t;
    cin >> p >> t;
    if (p == 1) {
        while (t--) {
            string str;
            cin >> str;
            n = str.length();
            for (int i = 0; i < str.length(); i++) s[i] = str[i];
            subtask1(true);
        }
    } else {
        lmao();
        while (t--) {
            cin >> n;
            cout << dp[n] << '\n';
        }
    }
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:176:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |             for (int i = 0; i < str.length(); i++) s[i] = str[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: 0 / 28