Submission #741393

# Submission time Handle Problem Language Result Execution time Memory
741393 2023-05-14T03:20:56 Z KoD parentrises (BOI18_parentrises) C++17
100 / 100
266 ms 213412 KB
// #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
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 240 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 240 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 240 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 4 ms 1264 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 5 ms 1236 KB Output is correct
21 Correct 20 ms 1056 KB Output is correct
22 Correct 31 ms 8932 KB Output is correct
23 Correct 17 ms 2028 KB Output is correct
24 Correct 22 ms 4648 KB Output is correct
25 Correct 32 ms 9444 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 260 ms 213372 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 260 ms 213372 KB Output is correct
2 Correct 259 ms 213412 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 260 ms 213372 KB Output is correct
2 Correct 259 ms 213412 KB Output is correct
3 Correct 266 ms 213304 KB Output is correct