oj.uz

Submission #59744

# Submission time Handle Problem Language Result Execution time Memory
59744 2018-07-23T03:42:00 Z model_code parentrises (BOI18_parentrises) C++17
100 / 100
 276 ms 15348 KB 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const string IMPOSSIBLE = "impossible";
const int MOD = (int) 1e9 + 7;

enum Color {
    GREEN = 'G',
    RED = 'R',
    BLUE = 'B',
};

template<class F>
string filter(const string& s, const F& pred) {
    string ret;
    for (int i = 0; i < (int) s.length(); ++i) {
        if (pred(i, s[i])) {
            ret += s[i];
        }
    }
    return ret;
}

bool check(string s) {
    int balance = 0;
    for (char c: s) {
        if (c == '(') {
            balance++;
        } else {
            balance--;
            if (balance < 0) {
                return false;
            }
        }
    }
    return balance == 0;
}

string reconstruct(string s) {
    int n = (int) s.length();
    vector<Color> color(n, Color::GREEN);
    vector<int> greenOpen, greenClosed;
    int balance = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            greenOpen.push_back(i);
            balance++;
        } else {
            balance--;
            greenClosed.push_back(i);
            if (balance < 0) {
                balance = 0;
                if (greenClosed.size() < 2U) {
                    return IMPOSSIBLE;
                }
                int pos1 = greenClosed.back();
                greenClosed.pop_back();
                int pos2 = greenClosed.back();
                greenClosed.pop_back();
                color[pos1] = Color::RED;
                color[pos2] = Color::BLUE;
            }
        }
    }
    while (balance-- > 0) {
        if (greenOpen.size() < 2U) {
            return IMPOSSIBLE;
        }
        int pos1 = greenOpen.back();
        greenOpen.pop_back();
        int pos2 = greenOpen.back();
        greenOpen.pop_back();
        color[pos1] = Color::RED;
        color[pos2] = Color::BLUE;
    }
    string s1 = filter(s, [&color](int index, char c) -> bool {
        return color[index] == Color::RED || color[index] == Color::GREEN;
    });
    string s2 = filter(s, [&color](int index, char c) -> bool {
        return color[index] == Color::BLUE || color[index] == Color::GREEN;
    });
    string ans;
    for (int i = 0; i < n; ++i) {
        ans += (char) color[i];
    }
    return (check(s1) && check(s2)) ? ans: IMPOSSIBLE;
}

vector<int> count(int n) {
    vector<vector<int>> dp(n + 5, vector<int>(2 * n + 5, 0));
    auto ndp = dp;
    vector<int> ans(n + 1);
    ans[0] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (auto& v: ndp) {
            fill(v.begin(), v.end(), 0);
        }
        for (int left = 0; left <= n; ++left) {
            for (int right = left; right <= 2 * i; ++right) {
                ndp[left + 1][right + 2] += dp[left][right];
                ndp[left + 1][right + 2] %= MOD;
                int nLeft = max(0, left - 2);
                int nRight = right - 1;
                if (nLeft <= nRight) {
                    ndp[nLeft][nRight] += dp[left][right];
                    ndp[nLeft][nRight] %= MOD;
                }
            }
        }
        ndp.swap(dp);
        ans[i] = 0;
        for (int right = 0; right <= 2 * i; ++right) {
            ans[i] += dp[0][right];
            ans[i] %= MOD;
        }
    }
    return ans;
}

int main() {
    int type;
    cin >> type;

    if (type == 1) {
        int T;
        cin >> T;

        while (T-- > 0) {
            string s;
            cin >> s;
            cout << reconstruct(move(s)) << '\n';
        }
    } else {
        int T;
        cin >> T;

        vector<int> qs(T);
        for (int& x: qs) {
            cin >> x;
        }
        vector<int> ans = count(*max_element(qs.begin(), qs.end()));
        for (int x: qs) {
            cout << ans[x] << '\n';
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 468 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 3 ms 544 KB Output is correct
2 Correct 3 ms 544 KB Output is correct
3 Correct 5 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 544 KB Output is correct
2 Correct 3 ms 544 KB Output is correct
3 Correct 5 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 628 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 544 KB Output is correct
2 Correct 3 ms 544 KB Output is correct
3 Correct 5 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 628 KB Output is correct
11 Correct 4 ms 628 KB Output is correct
12 Correct 4 ms 740 KB Output is correct
13 Correct 3 ms 740 KB Output is correct
14 Correct 3 ms 740 KB Output is correct
15 Correct 4 ms 912 KB Output is correct
16 Correct 29 ms 912 KB Output is correct
17 Correct 15 ms 2072 KB Output is correct
18 Correct 10 ms 2072 KB Output is correct
19 Correct 14 ms 2072 KB Output is correct
20 Correct 14 ms 2088 KB Output is correct
21 Correct 276 ms 2088 KB Output is correct
22 Correct 124 ms 15348 KB Output is correct
23 Correct 69 ms 15348 KB Output is correct
24 Correct 99 ms 15348 KB Output is correct
25 Correct 87 ms 15348 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15348 KB Output is correct
2 Correct 3 ms 15348 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15348 KB Output is correct
2 Correct 3 ms 15348 KB Output is correct
3 Correct 169 ms 15348 KB Output is correct