Submission #59748

#	Time	Username	Problem	Language	Result	Execution time	Memory
59748		model_code	parentrises (BOI18_parentrises)	C++17	16 / 100	1052 ms	106672 KiB

parentrises

#include <bits/stdc++.h>

using namespace std;

string SolveTest(string s) {
    vector<vector<pair<int, int>>> points(1, vector<pair<int, int>>(1, {0, 0}));
    int id = 0;
    for (auto ch : s) {
        const int sign = (ch == '(') ? +1 : -1;
        vector<pair<int, int>> new_row;
        for (auto&& p : points[id]) {
            int x, y; tie(x, y) = p;
            if (x + sign >= 0) {
                new_row.emplace_back(x + sign, y);
                if (y + sign >= 0) {
                    new_row.emplace_back(x + sign, y + sign);
                }
            }
            if (y + sign >= 0) {
                new_row.emplace_back(x, y + sign);
            }
        }
        
        sort(new_row.begin(), new_row.end());
        new_row.erase(unique(new_row.begin(), new_row.end()), new_row.end());
        
        points.push_back(move(new_row));
        ++id;
    }

    auto state = make_pair(0, 0);
    if (find(points[id].begin(), points[id].end(), state) == points[id].end()) {
        return "impossible";
    }

    reverse(s.begin(), s.end());

    string result = "";
    for (auto ch : s) {
        const int sign = (ch == ')') ? +1 : -1;
        int x, y; tie(x, y) = state;
        --id;

        if (binary_search(points[id].begin(), points[id].end(), make_pair(x + sign, y))) {
            x += sign;
            result += "R";
        } else if (binary_search(points[id].begin(), points[id].end(), make_pair(x, y + sign))) {
            y += sign;
            result += "B";
        } else {
            x += sign;
            y += sign;
            result += "G";
        }
        state = make_pair(x, y);
    }

    reverse(result.begin(), result.end());
    return result;
}

int main() {
    int type, num_tests; cin >> type >> num_tests;
    if (type == 2) {
        return 0;
    }

    while (num_tests--> 0) {
        string s; cin >> s;
        cout << SolveTest(s) << '\n';
    }
    return 0;
}

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