oj.uz

Submission #59749

# Submission time Handle Problem Language Result Execution time Memory
59749 2018-07-23T03:44:55 Z model_code parentrises (BOI18_parentrises) C++17
22 / 100
 250 ms 134408 KB 
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1000;

bitset<kMaxN + 1> dp[kMaxN + 1][kMaxN + 1];

string SolveTest(string s) {
    dp[0][0].set(0);
    int id = 0;
    for (auto ch : s) {
        for (int i = 0; i <= id + 1; ++i) {
            dp[id + 1][i].reset();
        }
        if (ch == '(') {
            for (int i = 0; i <= id; ++i) {
                dp[id + 1][i + 1] |= dp[id][i] << 1;
                dp[id + 1][i + 1] |= dp[id][i];
                dp[id + 1][i]     |= dp[id][i] << 1;
            }
        } else {
            for (int i = 1; i <= id; ++i) {
                dp[id + 1][i - 1] |= dp[id][i] >> 1;
                dp[id + 1][i - 1] |= dp[id][i];
                dp[id + 1][i]     |= dp[id][i] >> 1;
            }
        }
        ++id;
    }  
    
    if (not dp[id][0].test(0)) {
        return "impossible";
    }
    
    int x = 0, y = 0;
    string result = "";
    for (int i = id - 1; i >= 0; --i) {
        const int sign = (s[i] == ')') ? +1 : -1;
        if (x + sign >= 0 and dp[i][x + sign].test(y)) {
            x += sign;
            result += "R";
        } else if (y + sign >= 0 and dp[i][x].test(y + sign)) {
            y += sign;
            result += "B";
        } else {
            x += sign;
            y += sign;
            result += "G";
        }
    }
    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 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1164 KB Output is correct
2 Correct 4 ms 1548 KB Output is correct
3 Correct 2 ms 1548 KB Output is correct
4 Correct 3 ms 1548 KB Output is correct
5 Correct 5 ms 1596 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1164 KB Output is correct
2 Correct 4 ms 1548 KB Output is correct
3 Correct 2 ms 1548 KB Output is correct
4 Correct 3 ms 1548 KB Output is correct
5 Correct 5 ms 1596 KB Output is correct
6 Correct 94 ms 44220 KB Output is correct
7 Correct 124 ms 67288 KB Output is correct
8 Correct 9 ms 67288 KB Output is correct
9 Correct 38 ms 67288 KB Output is correct
10 Correct 137 ms 67308 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1164 KB Output is correct
2 Correct 4 ms 1548 KB Output is correct
3 Correct 2 ms 1548 KB Output is correct
4 Correct 3 ms 1548 KB Output is correct
5 Correct 5 ms 1596 KB Output is correct
6 Correct 94 ms 44220 KB Output is correct
7 Correct 124 ms 67288 KB Output is correct
8 Correct 9 ms 67288 KB Output is correct
9 Correct 38 ms 67288 KB Output is correct
10 Correct 137 ms 67308 KB Output is correct
11 Runtime error 250 ms 134408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

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

Subtask #6
0 / 16.0

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

Subtask #7
0 / 28.0

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