結果
問題 | No.1313 N言っちゃダメゲーム (4) |
ユーザー |
|
提出日時 | 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)#endiftemplate <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;}