Submission #365462

#	Time	Username	Problem	Language	Result	Execution time	Memory
365462		lookcook	parentrises (BOI18_parentrises)	C++17	56 / 100	1076 ms	4368 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 ways = 0;
void brute(int pos) {
    if (pos == n) {
        if (subtask1(false)) ways++;
        return;
    }
    s[pos] = '(';
    brute(pos+1);
    s[pos] = ')';
    brute(pos+1);
}

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 {
        while (t--) {
            cin >> n;
            ways = 0;
            brute(0);
            cout << ways << '\n';
        }
    }
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:141: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]
  141 |             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: 0 / 16
• Subtask 7: 0 / 28