結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0