#591566 (C++17) No.1313 N言っちゃダメゲーム (4)

• 問題: No.1313 N言っちゃダメゲーム (4)
• ユーザー: Haar
• 提出日時: 2020-12-10 10:13:54
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 481 ms / 2,000 ms
• コード長: 6,832 bytes
• コンパイル時間: 2,350 ms
• コンパイル使用メモリ: 204,556 KB
• 最終ジャッジ日時: 2025-01-16 21:17:47
• ジャッジサーバーID （参考情報）: judge2 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 35

ソースコード

#line 1 "main.cpp"
#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;
}

std::string YesNo(bool value){return value ? "Yes" : "No";}
std::string YESNO(bool value){return value ? "YES" : "NO";}
std::string yesno(bool value){return value ? "yes" : "no";}

template <typename T>
void putl(const T &value){
  std::cout << value << "\n";
}

template <typename Head, typename ... Tail>
void putl(const Head head, const Tail &... tail){
  std::cout << head << " ";
  putl(tail ...);
}


#line 6 "/home/haar/Downloads/kyopro-lib/Mylib/DataStructure/SegmentTree/segment_tree.cpp"

namespace haar_lib {
  template <typename Monoid>
  class segment_tree {
  public:
    using value_type = typename Monoid::value_type;

  private:
    Monoid M_;
    int depth_, size_, hsize_;
    std::vector<value_type> data_;

  public:
    segment_tree(){}
    segment_tree(int n):
      depth_(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1),
      size_(1 << depth_), hsize_(size_ / 2),
      data_(size_, M_())
    {}

    auto operator[](int i) const {
      assert(0 <= i and i < hsize_);
      return data_[hsize_ + i];
    }

    auto fold(int l, int r) const {
      assert(0 <= l and l <= r and r <= hsize_);
      value_type ret_left = M_();
      value_type ret_right = M_();

      int L = l + hsize_, R = r + hsize_;
      while(L < R){
        if(R & 1) ret_right = M_(data_[--R], ret_right);
        if(L & 1) ret_left = M_(ret_left, data_[L++]);
        L >>= 1, R >>= 1;
      }

      return M_(ret_left, ret_right);
    }

    auto fold_all() const {
      return data_[1];
    }

    void set(int i, const value_type &x){
      assert(0 <= i and i < hsize_);
      i += hsize_;
      data_[i] = x;
      while(i > 1) i >>= 1, data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    void update(int i, const value_type &x){
      assert(0 <= i and i < hsize_);
      i += hsize_;
      data_[i] = M_(data_[i], x);
      while(i > 1) i >>= 1, data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    template <typename T>
    void init_with_vector(const std::vector<T> &val){
      data_.assign(size_, M_());
      for(int i = 0; i < (int)val.size(); ++i) data_[hsize_ + i] = val[i];
      for(int i = hsize_; --i >= 1;) data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

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

  private:
    template <bool Lower, typename F>
    int bound(const int l, const int r, value_type x, F f) const {
      std::vector<int> pl, pr;
      int L = l + hsize_;
      int R = r + hsize_;
      while(L < R){
        if(R & 1) pr.push_back(--R);
        if(L & 1) pl.push_back(L++);
        L >>= 1, R >>= 1;
      }

      std::reverse(pr.begin(), pr.end());
      pl.insert(pl.end(), pr.begin(), pr.end());

      value_type a = M_();

      for(int i : pl){
        auto b = M_(a, data_[i]);

        if((Lower and not f(b, x)) or (not Lower and f(x, b))){
          while(i < hsize_){
            const auto c = M_(a, data_[i << 1 | 0]);
            if((Lower and not f(c, x)) or (not Lower and f(x, c))){
              i = i << 1 | 0;
            }else{
              a = c;
              i = i << 1 | 1;
            }
          }

          return i - hsize_;
        }

        a = b;
      }

      return r;
    }

  public:
    template <typename F = std::less<value_type>>
    int lower_bound(int l, int r, value_type x, F f = F()) const {
      return bound<true>(l, r, x, f);
    }

    template <typename F = std::less<value_type>>
    int upper_bound(int l, int r, value_type x, F f = F()) const {
      return bound<false>(l, r, x, f);
    }
  };
}
#line 2 "/home/haar/Downloads/kyopro-lib/Mylib/AlgebraicStructure/Monoid/bitor.cpp"

namespace haar_lib {
  template <typename T>
  struct bitor_monoid {
    using value_type = T;
    value_type operator()() const {return 0;}
    value_type operator()(value_type a, value_type b) const {return a | b;}
  };
}
#line 5 "/home/haar/Downloads/kyopro-lib/Mylib/IO/join.cpp"

namespace haar_lib {
  template <typename Iter>
  std::string join(Iter first, Iter last, std::string delim = " "){
    std::stringstream s;

    for(auto it = first; it != last; ++it){
      if(it != first) s << delim;
      s << *it;
    }

    return s.str();
  }
}
#line 69 "main.cpp"


namespace haar_lib {}

namespace solver {
  using namespace haar_lib;

  constexpr int m1000000007 = 1000000007;
  constexpr int m998244353 = 998244353;

  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, K; std::cin >> N >> K;
    std::string S; std::cin >> S;

    std::vector<bool> danger(N + 1);
    for(int i = 1; i <= N - 1; ++i){
      danger[i] = S[i - 1] == 'x';
    }
    danger[N] = true;

    dump(danger);

    segment_tree<bitor_monoid<bool>> seg(2 * N + 1);

    for(int i = N; i >= 0; --i){
      if(danger[i]){
        seg.set(i, false);
      }else{
        bool r = seg.fold(i + 1, i + K + 1);
        seg.set(i, not r);
      }
    }

    for(int i = 1; i <= N; ++i){
      std::cerr << (int)seg[i];
    }
    std::cerr << "\n";

    std::vector<int> ans;

    for(int i = 1; i <= K; ++i){
      if(seg[i]) ans.push_back(i);
    }

    if(ans.empty()){
      std::cout << 0 << "\n";
    }else{
      std::cout << join(ans.begin(), ans.end()) << "\n";
    }
  }
}

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