結果
問題 | No.1313 N言っちゃダメゲーム (4) |
ユーザー |
![]() |
提出日時 | 2020-12-14 11:48:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,013 bytes |
コンパイル時間 | 1,452 ms |
コンパイル使用メモリ | 107,092 KB |
最終ジャッジ日時 | 2025-02-23 16:21:33 |
合計ジャッジ時間 | 2,686 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /usr/include/c++/13/string:43, from /usr/include/c++/13/bitset:52, from main.cpp:6: /usr/include/c++/13/bits/allocator.h: In destructor ‘std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’: /usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /usr/include/c++/13/string:54: /usr/include/c++/13/bits/basic_string.h:181:14: note: called from here 181 | struct _Alloc_hider : allocator_type // TODO check __is_final | ^~~~~~~~~~~~
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <algorithm> #include <bitset> #include <climits> #include <cmath> #include <cstring> #include <deque> #include <forward_list> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef pair<int, int> P; typedef bitset<16> BS; const ll MOD = 1E+09 + 7; const ll INF = 1E18; const int MAX_N = 1 << 18; //1E+05を超える最小の二のべき乗131072 int N, K; bool dgr[MAX_N + 1]; //セグメント木を持つグローバル配列 int n, dat[2 * MAX_N - 1]; void init(int n_); void update(int k, int a); int query(int a, int b, int k, int l, int r); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> K; string s; cin >> s; for (int i = 0; i < s.size(); i++) { if (s[i] == 'x') { dgr[i + 1] = true; } } init(N + 1); for (int i = N - 1; i >= 0; i--) { if (!dgr[i] && query(i + 1, min(i + K, N) + 1, 0, 0, n) == 0) { update(i, 1); } } /* for (int i = 0; i <= N; i++) { cout << "i = " << i << ", dat = " << dat[i + n - 1] << "\n"; } */ vector<int> ans; for (int k = 1; k <= K; k++) { if (dat[k + n - 1] == 1) { ans.push_back(k); } } /* for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << "i = " << i << ", j = " << j << ", dp = " << dp[i][j] << "\n"; } } */ if (ans.size() == 0) { cout << "0\n"; } else { for (auto n : ans) { cout << n << "\n"; } } return 0; } //初期化 void init(int n_) { //簡単のため要素数を2のべき乗に n = 1; while (n < n_) { n *= 2; } //全ての値をINT_MAXに for (int i = 0; i < 2 * n - 1; i++) { dat[i] = 0; } } //k番目(0-indexed)の値をaに変更 void update(int k, int a) { //葉の節点 k += n - 1; dat[k] = a; //登りながら更新 while (k > 0) { k = (k - 1) / 2; dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2]; } } //[a,b)の最小値を求める //kは節点の番号、l,rはその節点が[l,r)に対応づいていることを示す //外からはquery(a, b, 0, 0, n)で呼ぶ int query(int a, int b, int k, int l, int r) { //[a,b)と[l,r)が交差しなければINT_MAX if (r <= a || b <= l) { return 0; } //[a,b)が[l,r)を完全に含んでいればこの節点の値を返す if (a <= l && r <= b) { return dat[k]; } else { //そうでなければ2つの子の最小値 int vl = query(a, b, k * 2 + 1, l, (l + r) / 2); int vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return vl + vr; } }