結果

問題 No.1219 Mancala Combo
ユーザー HaarHaar
提出日時 2020-09-04 22:22:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 198 ms / 2,000 ms
コード長 3,701 bytes
コンパイル時間 2,214 ms
コンパイル使用メモリ 199,624 KB
最終ジャッジ日時 2025-01-14 05:56:20
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()){
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1){
    return std::vector<T>(a[N - I], value);
  }else{
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}

/**
 * @title Dual segment tree
 * @docs dual_segment_tree.md
 */
template <typename Monoid>
class DualSegmentTree {
  using value_type = typename Monoid::value_type;
  const static Monoid M;

  const int depth, size, hsize;
  std::vector<value_type> data;

  void propagate(int i){
    if(i < hsize){
      data[i << 1 | 0] = M(data[i], data[i << 1 | 0]);
      data[i << 1 | 1] = M(data[i], data[i << 1 | 1]);
      data[i] = M();
    }
  }

  void propagate_top_down(int i){
    std::vector<int> temp;
    while(i > 1){
      i >>= 1;
      temp.push_back(i);
    }

    for(auto it = temp.rbegin(); it != temp.rend(); ++it) propagate(*it);
  }

public:
  DualSegmentTree(int n):
    depth(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1),
    size(1 << depth), hsize(size / 2),
    data(size, M())
  {}

  void update(int l, int r, const value_type &x){
    propagate_top_down(l + hsize);
    propagate_top_down(r + hsize);

    int L = l + hsize;
    int R = r + hsize;

    while(L < R){
      if(R & 1) --R, data[R] = M(x, data[R]);
      if(L & 1) data[L] = M(x, data[L]), ++L;
      L >>= 1, R >>= 1;
    }
  }

  value_type operator[](int i){
    propagate_top_down(i + hsize);
    return data[i + hsize];
  }

  template <typename T>
  void init_with_vector(const std::vector<T> &a){
    data.assign(size, M());
    for(int i = 0; i < (int)a.size(); ++i) data[hsize + i] = a[i];
  }

  template <typename T>
  void init(const T &val){
    init_with_vector(std::vector<value_type>(hsize, val));
  }
};

/**
 * @title Sum monoid
 * @docs sum.md
 */
template <typename T>
struct SumMonoid {
  using value_type = T;
  value_type operator()() const {return 0;}
  value_type operator()(value_type a, value_type b) const {return a + b;}
};


namespace solver{
  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  void solve(){
    int N; std::cin >> N;
    std::vector<int> A(N + 1);
    for(int i = 1; i <= N; ++i) std::cin >> A[i];

    DualSegmentTree<SumMonoid<int64_t>> seg(N + 1);
    seg.init_with_vector(A);

    bool ok = true;

    for(int i = N; i > 0; --i){
      auto x = seg[i];
      if(x % i == 0){
        seg.update(0, i, x / i);
      }else{
        ok = false;
        break;
      }
    }

    std::cout << (ok ? "Yes" : "No") << "\n";
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
    }catch(const std::istream::failure &e){
      break;
    }
  }
  return 0;
}
0