Submission #741393

#	Time	Username	Problem	Language	Result	Execution time	Memory
741393		KoD	parentrises (BOI18_parentrises)	C++17	100 / 100	266 ms	213412 KiB

parentrises

// #define MULTEST

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

namespace kod {
namespace util {

template <class F> class FixedPoint : private F {
    constexpr FixedPoint(F&& f) noexcept : F(std::forward<F>(f)) {}
    template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;

  public:
    template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
    using F = std::decay_t<G>;
    return FixedPoint<F>(std::forward<F>(g));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

class ForwardLoop {
    int x, y;
    constexpr ForwardLoop(int x, int y) noexcept : x(x), y(y) {}
    friend constexpr ForwardLoop rep(int, int) noexcept;
    friend constexpr ForwardLoop rep(int) noexcept;

  public:
    constexpr ForwardLoop begin() const noexcept { return *this; }
    constexpr std::monostate end() const noexcept { return {}; }
    constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
    constexpr void operator++() const noexcept {}
    constexpr int operator*() noexcept { return x++; }
};

[[nodiscard]] constexpr ForwardLoop rep(int l, int r) noexcept { return ForwardLoop(l, r); }
[[nodiscard]] constexpr ForwardLoop rep(int n) noexcept { return ForwardLoop(0, n); }

class BackwardLoop {
    int x, y;
    constexpr BackwardLoop(int x, int y) noexcept : x(x), y(y) {}
    friend constexpr BackwardLoop revrep(int, int) noexcept;
    friend constexpr BackwardLoop revrep(int) noexcept;

  public:
    constexpr BackwardLoop begin() const noexcept { return *this; }
    constexpr std::monostate end() const noexcept { return {}; }
    constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
    constexpr void operator++() const noexcept {}
    constexpr int operator*() noexcept { return --x; }
};

[[nodiscard]] constexpr BackwardLoop revrep(int l, int r) noexcept { return BackwardLoop(r, l); }
[[nodiscard]] constexpr BackwardLoop revrep(int n) noexcept { return BackwardLoop(n, 0); }

template <class F> constexpr void repeat(int n, const F& f) noexcept {
    assert(n >= 0);
    while (n--) f();
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

namespace stdio_impl {

template <class T> T scan() {
    T x;
    std::cin >> x;
    return x;
}
struct scan_any {
    template <class T> operator T() const { return scan<T>(); }
};

}  // namespace stdio_impl

template <class T = void> decltype(auto) scan() {
    if constexpr (std::is_same_v<T, void>)
        return stdio_impl::scan_any{};
    else
        return stdio_impl::scan<T>();
}
template <class T, std::size_t N> std::array<T, N> scan_arr() {
    std::array<T, N> a;
    for (auto& x : a) x = scan<T>();
    return a;
}
template <class T> std::vector<T> scan_vec(int n) {
    if (n == -1) n = scan<int>();
    assert(n >= 0);
    std::vector<T> v;
    v.reserve(n);
    while (n--) v.push_back(scan<T>());
    return v;
}

void flush() { std::cout << std::flush; }
void print() {}
template <class T, class... Args> void print(const T& x, const Args&... args) {
    std::cout << x;
    if (sizeof...(args) != 0) std::cout << ' ';
    print(args...);
}
template <class... Args> void println(const Args&... args) {
    print(args...);
    std::cout << '\n';
}
template <class C> void print_seq(const C& c, const char* sep = " ", const char* end = "\n") {
    bool f = false;
    for (const auto& x : c) {
        if (f)
            std::cout << sep;
        else
            f = true;
        std::cout << x;
    }
    std::cout << end;
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace sol {

using ll = long long;
using uint = unsigned;
using ull = unsigned long long;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using namespace util;

constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;

constexpr ll floor_div(ll x, ll y) noexcept {
    assert(y != 0);
    return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
    assert(y != 0);
    return x / y + ((x ^ y) >= 0 && x % y != 0);
}

template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

void run();

}  // namespace sol
}  // namespace kod

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(20);
    int cases = 1;
#ifdef MULTEST
    std::cin >> cases;
#endif
    while (cases--) kod::sol::run();
    return 0;
}

#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif

namespace kod {
namespace mod {

namespace finite_field_impl {

constexpr bool is_valid_mod(unsigned m) noexcept {
    if (m <= 1 || (1u << 31) <= m) return false;
    for (unsigned i = 2; i * i <= m; ++i) {
        if (m % i == 0) return false;
    }
    return true;
}

constexpr long long rem_euclid(long long x, long long y) noexcept {
    if (x >= 0) return x < y ? x : x % y;
    if (x >= -y) return x + y;
    return (x %= y) == 0 ? 0 : x + y;
}

template <unsigned MOD, std::enable_if_t<is_valid_mod(MOD)>* = nullptr> class FiniteField {
  public:
    constexpr FiniteField() noexcept : v(0) {}
    constexpr FiniteField(long long x) noexcept : v(rem_euclid(x, MOD)) {}

    constexpr FiniteField& operator+=(const FiniteField& x) noexcept {
        v += x.v;
        if (v >= MOD) v -= MOD;
        return *this;
    }
    constexpr FiniteField& operator-=(const FiniteField& x) noexcept {
        if (v < x.v) v += MOD;
        v -= x.v;
        return *this;
    }
    constexpr FiniteField& operator*=(const FiniteField& x) noexcept {
        v = (unsigned long long)v * x.v % MOD;
        return *this;
    }
    constexpr FiniteField& operator/=(const FiniteField& x) noexcept { return *this *= x.inv(); }

    constexpr FiniteField operator+() const noexcept { return *this; }
    constexpr FiniteField operator-() const noexcept { return raw(v == 0 ? 0 : MOD - v); }
    friend constexpr FiniteField operator+(FiniteField x, const FiniteField& y) noexcept {
        return x += y;
    }
    friend constexpr FiniteField operator-(FiniteField x, const FiniteField& y) noexcept {
        return x -= y;
    }
    friend constexpr FiniteField operator*(FiniteField x, const FiniteField& y) noexcept {
        return x *= y;
    }
    friend constexpr FiniteField operator/(FiniteField x, const FiniteField& y) noexcept {
        return x /= y;
    }
    friend constexpr bool operator==(const FiniteField& x, const FiniteField& y) noexcept {
        return x.v == y.v;
    }
    friend constexpr bool operator!=(const FiniteField& x, const FiniteField& y) noexcept {
        return x.v != y.v;
    }
    friend std::ostream& operator<<(std::ostream& s, const FiniteField& x) noexcept {
        return s << x.v;
    }

    constexpr unsigned val() const noexcept { return v; }
    constexpr FiniteField inv() const noexcept { return pow(MOD - 2); }
    constexpr FiniteField pow(long long e) const noexcept {
        if (v == 0) {
            assert(e >= 0);
            return raw(e == 0);
        }
        unsigned long long x = 1, y = v;
        for (e = rem_euclid(e, MOD - 1); e > 0; e >>= 1) {
            if (e & 1) x = x * y % MOD;
            y = y * y % MOD;
        }
        return raw(x);
    }

    static constexpr unsigned mod() noexcept { return MOD; }
    static constexpr FiniteField raw(unsigned x) noexcept {
        FiniteField ret;
        ret.v = x;
        return ret;
    }

    static FiniteField fact(int n) noexcept {
        assert(n >= 0);
        static std::vector v = {raw(1)};
        for (int i = v.size(); i <= n; ++i) v.push_back(v.back() * FiniteField(i));
        return v[n];
    }
    static FiniteField inv(int n) noexcept {
        assert(n >= 1);
        static std::vector v = {raw(0), raw(1)};
        for (int i = v.size(); i <= n; ++i) v.push_back(-raw(mod() / i) * v[mod() % i]);
        return v[n];
    }
    static FiniteField ifact(int n) noexcept {
        assert(n >= 0);
        static std::vector v = {raw(1)};
        for (int i = v.size(); i <= n; ++i) v.push_back(v.back() * inv(i));
        return v[n];
    }
    static FiniteField factpow(int n, int d) noexcept {
        return 0 <= d && d <= n ? fact(n) * ifact(n - d) : raw(0);
    }
    static FiniteField binom(int n, int d) noexcept {
        return 0 <= d && d <= n ? factpow(n, d) * ifact(d) : raw(0);
    }
    static FiniteField nbinom(int n, int d) noexcept {
        return n >= 0 && d >= 0 ? (n == 0 ? raw(d == 0) : binom(n + d - 1, d)) : raw(0);
    }

  private:
    unsigned v;
};

}  // namespace finite_field_impl

using finite_field_impl::FiniteField;
using F_998244353 = FiniteField<998244353>;
using F_1000000007 = FiniteField<1000000007>;

}  // namespace mod
}  // namespace kod

namespace kod {
namespace sol {

using Fp = mod::F_1000000007;

string solve1(const string& S) {
    const int N = (int)S.size();
    {
        int up = 0, down = 0;
        for (const int i : rep(N)) {
            up += (S[i] == '(');
            down += (S[i] == ')');
            if (up - (down + 1) / 2 < 0) {
                return "impossible";
            }
        }
        up = down = 0;
        for (const int i : revrep(N)) {
            up += (S[i] == ')');
            down += (S[i] == '(');
            if (up - (down + 1) / 2 < 0) {
                return "impossible";
            }
        }
    }
    vector<int> type(N);
    for (const int p : rep(2)) {
        vector<int> up, down;
        vector<char> use(N);
        int pos = 0, min = 0;
        {
            int s = 0, t = 0;
            for (const int i : rep(N)) {
                if (S[i] == '(') {
                    use[i] = (s == p);
                    if (use[i]) {
                        pos += (s == p);
                    } else {
                        up.push_back(i);
                    }
                    s ^= 1;
                } else {
                    use[i] = (t == p);
                    if (use[i]) {
                        pos -= (t == p);
                    } else {
                        down.push_back(i);
                    }
                    t ^= 1;
                }
                setmin(min, pos);
            }
        }
        for (const int i : rep(std::max(0, -min))) {
            use[up[i]] = true;
            pos += 1;
        }
        std::reverse(down.begin(), down.end());
        for (const int i : rep(pos)) {
            use[down[i]] = true;
        }
        for (const int i : rep(N)) {
            type[i] |= (int)use[i] << p;
        }
    }
    string ret;
    for (const int x : type) {
        ret += "RBG"[x - 1];
    }
    return ret;
}

Fp solve2(const int N) {
    constexpr int max_n = 300;
    static array<array<array<Fp, max_n + 1>, max_n + 1>, 2 * max_n + 1> dp = {};
    static bool init = true;

    if (init) {
        init = false;
        for (const int ub : rep(2 * max_n + 1)) {
            dp[ub][0][0] = 1;
            for (const int i : rep(max_n + 1)) {
                for (const int j : rep(max_n + 1)) {
                    if (2 * i - j < 0 || 2 * j - i > ub) {
                        dp[ub][i][j] = 0;
                        continue;
                    }
                    if (i < max_n) dp[ub][i + 1][j] += dp[ub][i][j];
                    if (j < max_n) dp[ub][i][j + 1] += dp[ub][i][j];
                }
            }
        }
    }

    Fp ret = 0;
    for (const int m : rep(N + 1)) {
        if (const int ub = 2 * N - 3 * m; ub >= 0) {
            ret += dp[ub][m][N - m];
        }
    }
    return ret;
}

void run() {
    const int P = scan();
    if (P == 1) {
        repeat(scan<int>(), [&] { println(solve1(scan<string>())); });
    } else {
        repeat(scan<int>(), [&] { println(solve2(scan<int>())); });
    }
}

}  // namespace sol
}  // namespace kod

• 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