oj.uz

Submission #491380

# Submission time Handle Problem Language Result Execution time Memory
491380 2021-12-01T21:26:41 Z regex0754 Kangaroo (CEOI16_kangaroo) C++17
100 / 100
 383 ms 219976 KB 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;

using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k) -> iterator of kth element (in sorted fashion : low - high)
// order_of_key(x) -> #numbers strictly less than x

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define sync ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
#define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
#define fi first
#define se second
#define endl '\n'
 
using ll = long long
;using ld = long double;
using pii = pair<int , int>;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(0);

const int mod = 1e9 + 7;
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }

  Modular inverse() const {
    Type a = value, b = mod(), u = 0, v = 1;
    while (a != 0) {
      Type t = b / a;
      b -= t * a; swap(a, b);
      u -= t * v; swap(u, v);
    }
    assert(b == 1);
    return Modular(u);
  }
  Modular& operator/=(const Modular& other) { return *this *= other.inverse(); }

  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}

template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  stream >> number.value;
  number.value = Modular<T>::normalize(number.value);
  return stream;
}

struct VarMod { static int value; };
int VarMod::value;

using mint = Modular<std::integral_constant<int, mod>>;

int main(){
  sync

  int tt = 1;
  //cin >> tt;

  while(tt--){
    int n, s, e;
    cin >> n >> s >> e;
    vector<vector<vector<mint>>> dp(n + 1, vector<vector<mint>>(n + 1, vector<mint>(4)));
    for (int i = 0; i <= n; i++){
      if (i){
        if (i == s or i == e){
          dp[i] = dp[i - 1];
          continue;
        }
        for (int pc = 2; pc <= n - 1; pc++){
          for (int msk = 0; msk < 4; msk++){
            //merge edge
            if (pc != 2){
              int l = ((msk >> 1) ? 1 : (i > s));
              if (l)
                dp[i][pc - 1][msk | 2] += dp[i - 1][pc][msk];
              int r = ((msk & 1) ? 1 : (i > e));
              if (r)
                dp[i][pc - 1][msk | 1] += dp[i - 1][pc][msk];
            } 
            else{
              int l = ((msk >> 1) ? 1 : (i > s));
              int r = ((msk & 1) ? 1 : (i > e));
              if (l && r){
                dp[i][pc - 1][3] += dp[i - 1][pc][msk];
              }
            }
            // merge inside component
            dp[i][pc - 1][msk] += (max(0, (pc - 3)) * dp[i - 1][pc][msk]);
            // append only possible for edge components
            if (i < s && 1 - (msk >> 1)){
              dp[i][pc][msk | 2] += dp[i - 1][pc][msk];
            }
            if (i < e && 1 - (msk & 1)){
              dp[i][pc][msk | 1] += dp[i - 1][pc][msk];
            }
            // new component
            dp[i][pc + 1][msk] += ((pc - 1) * dp[i - 1][pc][msk]);
          }
        }
      }
      else{
        if (n == 2) dp[0][1][3] = 1;
        else dp[0][2][0] = 1;
      }
    }
    // for (int i = 1; i <= n; i++){
    //   for (int j = 1; j <= n; j++){
    //     for (int msk = 0; msk < 4; msk++){
    //       cout << i << " " << j << " " << bitset<2>(msk) << " " << dp[i][j][msk] << endl;
    //     } 
    //   }
    // }
    cout << dp[n][1][3] << endl;
  }

  cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s    ";
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 4 ms 2508 KB Output is correct
13 Correct 6 ms 2252 KB Output is correct
14 Correct 4 ms 2508 KB Output is correct
15 Correct 6 ms 2548 KB Output is correct
16 Correct 4 ms 2508 KB Output is correct
17 Correct 5 ms 2492 KB Output is correct
18 Correct 3 ms 1996 KB Output is correct
19 Correct 5 ms 2380 KB Output is correct
20 Correct 4 ms 2508 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 4 ms 2508 KB Output is correct
13 Correct 6 ms 2252 KB Output is correct
14 Correct 4 ms 2508 KB Output is correct
15 Correct 6 ms 2548 KB Output is correct
16 Correct 4 ms 2508 KB Output is correct
17 Correct 5 ms 2492 KB Output is correct
18 Correct 3 ms 1996 KB Output is correct
19 Correct 5 ms 2380 KB Output is correct
20 Correct 4 ms 2508 KB Output is correct
21 Correct 40 ms 24068 KB Output is correct
22 Correct 45 ms 27288 KB Output is correct
23 Correct 55 ms 31684 KB Output is correct
24 Correct 383 ms 219928 KB Output is correct
25 Correct 377 ms 219976 KB Output is correct
26 Correct 378 ms 219972 KB Output is correct
27 Correct 367 ms 217828 KB Output is correct
28 Correct 212 ms 123496 KB Output is correct