Submission #59747

#	Time	Username	Problem	Language	Result	Execution time	Memory
59747		model_code	parentrises (BOI18_parentrises)	C++17	100 / 100	468 ms	226796 KiB

parentrises

#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 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28