oj.uz

Submission #639823

# Submission time Handle Problem Language Result Execution time Memory
639823 2022-09-12T04:31:26 Z lunchbox parentrises (BOI18_parentrises) C++17
100 / 100
 69 ms 3364 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
  #include "lib/debug.h"
#else
  #define debug(...) 0
#endif

template<int Rt, int Md>
struct Mi {
  static constexpr uint32_t get_r() {
    uint32_t iv = Md;
    for (uint32_t i = 0; i != 4; ++i)
      iv *= 2 - Md * iv;
    return iv;
  }
  static constexpr uint32_t r1 = -get_r(), r2 = -uint64_t(Md) % Md;
  uint32_t x;
 
  Mi() = default;
  ~Mi() = default;
  constexpr Mi(uint32_t x) : x(rd(uint64_t(x) * r2)) {}
  constexpr Mi(const Mi &r) : x(r.x) {}
  static constexpr int root() {
    return Rt;
  }
  static constexpr int mod() {
    return Md;
  }
  static constexpr uint32_t rd(uint64_t x) {
    return (x + (uint64_t(uint32_t(x) * r1) * Md)) >> 32;
  }
  constexpr uint32_t get() const {
    uint32_t r = rd(x);
    return r - (Md & -(r >= Md));
  }
  explicit constexpr operator int32_t() const {
    return int32_t(get());
  }
  constexpr Mi &operator=(const Mi &r) {
    return x = r.x, *this;
  }
  constexpr Mi operator-() const {
    Mi r;
    return r.x = (Md << 1 & -(x != 0)) - x, r;
  }
  constexpr Mi inv() const {
    return bp(-1);
  }
  constexpr Mi &operator+=(const Mi &r) {
    return x += r.x - (Md << 1), x += Md << 1 & -(int32_t(x) < 0), *this;
  }
  constexpr Mi &operator-=(const Mi &r) {
    return x -= r.x, x += Md << 1 & -(int32_t(x) < 0), *this;
  }
  constexpr Mi &operator*=(const Mi &r) {
    return x = rd(uint64_t(x) * r.x), *this;
  }
  constexpr Mi &operator/=(const Mi &r) {
    return this->operator*=(r.inv());
  }
  friend Mi operator+(const Mi &l, const Mi &r) {
    return Mi(l) += r;
  }
  friend Mi operator-(const Mi &l, const Mi &r) {
    return Mi(l) -= r;
  }
  friend Mi operator*(const Mi &l, const Mi &r) {
    return Mi(l) *= r;
  }
  friend Mi operator/(const Mi &l, const Mi &r) {
    return Mi(l) /= r;
  }
  friend std::istream &operator>>(std::istream &is, Mi &r) {
    return is >> r.x, r.x = rd(uint64_t(r.x) * r2), is;
  }
  friend std::ostream &operator<<(std::ostream &os, const Mi &r) {
    return os << r.get();
  }
  constexpr Mi bp(int64_t k) const {
    if ((k %= Md - 1) < 0)
      k += Md - 1;
    Mi p(1), a(*this);
    for ( ; k != 0; k >>= 1, a *= a)
      if (k & 1)
        p *= a;
    return p;
  }
};

typedef Mi<3, (int) 1e9 + 7> mi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int p;
  cin >> p;
  int t;
  cin >> t;
  if (p == 1)
    while (t--) {
      string s;
      cin >> s;
      int l = 0, r = 0, yes = 1;
      for (char c : s)
        if (c == '(')
          l += 1, r += 2;
        else {
          l -= 2, r -= 1;
          l = max(l, 0);
          if (r < 0)
            yes = 0;
        }
      yes &= l <= 0 && r >= 0;
      if (!yes) {
        cout << "impossible" << '\n';
        continue;
      }
      int n = s.size(), o = 0, i = n - 1;
      string t(n, 'G');
      for (i = n - 1; r > 0 && i >= 0; i--, r--)
        if (s[i] == '(')
          t[i] = "RB"[o ^= 1];
      o = 0;
      while (i >= 0) {
        if (s[i] == ')')
          t[i] = "RB"[o ^= 1];
        i--;
      }
      cout << t << '\n';
    }
  else {
    const int N = 300, L = 200, R = 400;
    static mi f[L + 1][R + 1], g[L + 1][R + 1], h[N + 1];
    f[0][0] = 1;
    for (int t = 1; t <= N; t++) {
      memset(g, 0, sizeof g);
      for (int l = 0; l <= L; l++)
        for (int r = 0; r <= R; r++) {
          if (l + 1 <= L && r + 2 <= R)
            g[l + 1][r + 2] += f[l][r];
          if (r - 1 >= 0)
            g[max(0, l - 2)][r - 1] += f[l][r];
        }
      swap(f, g);
      for (int i = 0; i <= R; i++)
        h[t] += f[0][i];
    }
    while (t--) {
      int n;
      cin >> n;
      cout << h[n] << '\n';
    }
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
6.0 / 6.0

# 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 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

Subtask #4
28.0 / 28.0

# 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 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 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 548 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 16 ms 984 KB Output is correct
22 Correct 13 ms 3312 KB Output is correct
23 Correct 9 ms 1320 KB Output is correct
24 Correct 11 ms 1856 KB Output is correct
25 Correct 14 ms 3364 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 852 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 852 KB Output is correct
2 Correct 66 ms 932 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 852 KB Output is correct
2 Correct 66 ms 932 KB Output is correct
3 Correct 69 ms 936 KB Output is correct