oj.uz

Submission #59748

# Submission time Handle Problem Language Result Execution time Memory
59748 2018-07-23T03:44:25 Z model_code parentrises (BOI18_parentrises) C++17
16 / 100
 1000 ms 106672 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 3 ms 524 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 648 KB Output is correct
2 Correct 16 ms 2188 KB Output is correct
3 Correct 4 ms 2188 KB Output is correct
4 Correct 3 ms 2188 KB Output is correct
5 Correct 11 ms 2188 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 648 KB Output is correct
2 Correct 16 ms 2188 KB Output is correct
3 Correct 4 ms 2188 KB Output is correct
4 Correct 3 ms 2188 KB Output is correct
5 Correct 11 ms 2188 KB Output is correct
6 Execution timed out 1052 ms 106672 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 648 KB Output is correct
2 Correct 16 ms 2188 KB Output is correct
3 Correct 4 ms 2188 KB Output is correct
4 Correct 3 ms 2188 KB Output is correct
5 Correct 11 ms 2188 KB Output is correct
6 Execution timed out 1052 ms 106672 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 106672 KB Unexpected end of file - int32 expected

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 106672 KB Unexpected end of file - int32 expected

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 106672 KB Unexpected end of file - int32 expected