oj.uz

Submission #59747

# Submission time Handle Problem Language Result Execution time Memory
59747 2018-07-23T03:43:48 Z model_code parentrises (BOI18_parentrises) C++17
100 / 100
 468 ms 226796 KB 
#include <bits/stdc++.h>

using namespace std;

namespace count {

const int kMaxN = 300, kMod = 1e9 + 7;

struct ModInt {
    int n;

    ModInt(const int n_ = 0) : n(n_ % kMod) {}

    operator int() {
        return n;
    }
};

ModInt& operator +=(ModInt& a, const ModInt& b) {
    a.n += b.n;
    if (a.n >= kMod) {
        a.n -= kMod;
    }
    return a;
}

ModInt dp[kMaxN + 1][kMaxN + 1][2 * (kMaxN + 1)];

void Init() {
    dp[0][0][1] = 1;
    for (int i = 0; i < kMaxN; ++i) {
        for (int j = 0; j <= i; ++j) {
            for (int k = 1; k <= 2 * i + 1; ++k) {
                dp[i + 1][j + 1][k + 2]         += dp[i][j][k];  // place '('
                dp[i + 1][max(0, j - 2)][k - 1] += dp[i][j][k];  // place ')'
            }
        }
    }
}

int CountSolutions(int n) {
    ModInt ans;
    for (int i = 1; i <= 2 * n + 1; ++i) {
        ans += dp[n][0][i];
    }
    return ans;
}

}  // namespace count

namespace reconstruct {

string Solve(string s) {
    vector<pair<int, int>> diagonals{make_pair(-1, 1)};
    for (auto ch : s) {
        int d1, d2; tie(d1, d2) = diagonals.back();
        if (ch == '(') {
            d1 += 1;
            d2 += 2;
        } else {
            d1 -= 2;
            d2 -= 1;
        }

        if (d1 < -1) {
            d1 = -1;
        }

        if (d2 <= 0) {
            return "impossible";
        }
        diagonals.emplace_back(d1, d2);
    }

    if (diagonals.back().first >= 0) {
        return "impossible";
    }

    int x = 0, y = 0;
    string result = "";
    for (int i = (int)s.length() - 1; i >= 0; --i) {
        const int sign = (s[i] == ')') ? +1 : -1;
        int d1, d2; tie(d1, d2) = diagonals[i];
        if (x + y + sign <= d1 or x + y + sign >= d2) {
            result += "G";
            x += sign;
            y += sign;
        } else if (x + sign >= 0 and x + sign < d2 / 2 + 1) {
            result += "R";
            x += sign;
        } else {
            result += "B";
            y += sign;
        }
    }
    return string(result.rbegin(), result.rend());
}

}  // namespace reconstruct

int main() {
    int type, num_tests; cin >> type >> num_tests;
    if (type == 2) {
        count::Init();
        while (num_tests--> 0) {
            int n; cin >> n;
            cout << count::CountSolutions(n) << '\n';
        }
    } else {
        while (num_tests--> 0) {
            string s; cin >> s;
            cout << reconstruct::Solve(s) << '\n';
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 213752 KB Output is correct
2 Correct 182 ms 213752 KB Output is correct
3 Correct 202 ms 213768 KB Output is correct
4 Correct 188 ms 213896 KB Output is correct
5 Correct 192 ms 213896 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 213896 KB Output is correct
2 Correct 175 ms 213972 KB Output is correct
3 Correct 189 ms 213972 KB Output is correct
4 Correct 198 ms 213972 KB Output is correct
5 Correct 189 ms 213972 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 213896 KB Output is correct
2 Correct 175 ms 213972 KB Output is correct
3 Correct 189 ms 213972 KB Output is correct
4 Correct 198 ms 213972 KB Output is correct
5 Correct 189 ms 213972 KB Output is correct
6 Correct 223 ms 214124 KB Output is correct
7 Correct 226 ms 214124 KB Output is correct
8 Correct 224 ms 214124 KB Output is correct
9 Correct 211 ms 214124 KB Output is correct
10 Correct 201 ms 214124 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 213896 KB Output is correct
2 Correct 175 ms 213972 KB Output is correct
3 Correct 189 ms 213972 KB Output is correct
4 Correct 198 ms 213972 KB Output is correct
5 Correct 189 ms 213972 KB Output is correct
6 Correct 223 ms 214124 KB Output is correct
7 Correct 226 ms 214124 KB Output is correct
8 Correct 224 ms 214124 KB Output is correct
9 Correct 211 ms 214124 KB Output is correct
10 Correct 201 ms 214124 KB Output is correct
11 Correct 200 ms 214124 KB Output is correct
12 Correct 188 ms 214224 KB Output is correct
13 Correct 176 ms 214224 KB Output is correct
14 Correct 201 ms 214224 KB Output is correct
15 Correct 189 ms 214320 KB Output is correct
16 Correct 217 ms 214320 KB Output is correct
17 Correct 195 ms 215416 KB Output is correct
18 Correct 211 ms 215416 KB Output is correct
19 Correct 227 ms 215416 KB Output is correct
20 Correct 211 ms 215544 KB Output is correct
21 Correct 468 ms 215544 KB Output is correct
22 Correct 280 ms 226796 KB Output is correct
23 Correct 260 ms 226796 KB Output is correct
24 Correct 259 ms 226796 KB Output is correct
25 Correct 273 ms 226796 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 226796 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 226796 KB Output is correct
2 Correct 278 ms 226796 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 226796 KB Output is correct
2 Correct 278 ms 226796 KB Output is correct
3 Correct 304 ms 226796 KB Output is correct