結果

問題 No.1313 N言っちゃダメゲーム (4)
ユーザー HaarHaar
提出日時 2020-12-10 08:56:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,582 bytes
コンパイル時間 2,489 ms
コンパイル使用メモリ 228,320 KB
実行使用メモリ 13,568 KB
最終ジャッジ日時 2024-09-19 16:44:26
合計ジャッジ時間 4,744 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 WA -
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,948 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 WA -
testcase_09 AC 2 ms
6,944 KB
testcase_10 WA -
testcase_11 AC 2 ms
6,944 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 58 ms
13,568 KB
testcase_16 AC 70 ms
8,960 KB
testcase_17 AC 21 ms
6,944 KB
testcase_18 AC 38 ms
8,704 KB
testcase_19 AC 36 ms
7,396 KB
testcase_20 AC 5 ms
6,944 KB
testcase_21 AC 26 ms
6,944 KB
testcase_22 AC 15 ms
6,944 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
権限があれば一括ダウンロードができます

ソースコード

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;
}

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 ...);
}

namespace haar_lib {
  class integer_set {
    std::map<int64_t, int64_t> data_;
    using citer = typename std::map<int64_t, int64_t>::const_iterator;

    std::optional<citer> get_interval(int64_t x) const {
      if(data_.empty()) return std::nullopt;
      auto next = data_.lower_bound(x);
      if(next == data_.end()){
        auto prev = std::prev(next);
        if(x <= prev->second) return {prev};
        return std::nullopt;
      }
      if(next->first == x) return {next};
      if(next == data_.begin()) return std::nullopt;
      auto prev = std::prev(next);
      if(x <= prev->second) return {prev};
      return std::nullopt;
    }

  public:
    integer_set(){}

    bool contains(int64_t x) const {
      return (bool)get_interval(x);
    }

    void add(int64_t x){
      if(data_.empty()){
        data_[x] = x;
        return;
      }

      auto next = data_.lower_bound(x);
      if(next == data_.end()){
        auto prev = std::prev(next);
        if(x <= prev->second) return;
        if(prev->second + 1 == x){
          prev->second = x;
        }else{
          data_[x] = x;
        }
        return;
      }
      if(next->first == x) return;

      if(next == data_.begin()){
        if(x + 1 == next->first){
          auto t = next->second;
          data_.erase(next);
          data_[x] = t;
        }else{
          data_[x] = x;
        }
        return;
      }

      auto prev = std::prev(next);
      if(x <= prev->second) return;
      if(prev->second + 1 == x){
        prev->second = x;

        if(prev->second + 1 == next->first){
          prev->second = next->second;
          data_.erase(next);
        }
      }else if(x + 1 == next->first){
        auto t = next->second;
        data_.erase(next);
        data_[x] = t;
      }else{
        data_[x] = x;
      }

      return;
    }

    void erase(int64_t x){
      const auto res = get_interval(x);
      if(res){
        const auto it = res.value();
        const auto [l, r] = *it;
        data_.erase(it);
        if(l <= x - 1) data_[l] = x - 1;
        if(x + 1 <= r) data_[x + 1] = r;
      }
    }

    int64_t mex(int64_t x) const {
      auto res = get_interval(x);
      if(res) return (*res)->second + 1;
      return x;
    }
  };
};

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();
  }
}



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);

    std::vector<int> g(N + 1);

    integer_set iset;
    std::map<int, int> count;

    for(int i = N; i >= 0; --i){
      if(i + K + 1 <= N){
        count[g[i + K + 1]] -= 1;
        if(count[g[i + K + 1]] == 0){
          iset.erase(g[i + K + 1]);
        }
      }

      if(danger[i]){
        g[i] = 0;
      }else{
        g[i] = iset.mex(0);
      }

      iset.add(g[i]);
      count[g[i]] += 1;
    }

    dump(g);

    std::vector<int> ans;

    for(int i = 1; i <= K; ++i){
      if(g[i + 1] == 0) 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;
}
0