結果
問題 | No.1770 N言っちゃダメゲーム (6) |
ユーザー |
|
提出日時 | 2021-12-03 20:31:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,373 bytes |
コンパイル時間 | 2,219 ms |
コンパイル使用メモリ | 203,660 KB |
最終ジャッジ日時 | 2025-01-26 03:11:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:21:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 21 | int n, k; scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std::literals::string_literals; using i64 = std::int_fast64_t; using std::cout; using std::cerr; using std::endl; using std::cin; #if defined(DONLINE_JUDGE) #define NDEBUG #elif defined(ONLINE_JUDGE) #define NDEBUG #endif template<typename T> std::vector<T> make_v(size_t a){return std::vector<T>(a);} template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts){ return std::vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } int main() { int n, k; scanf("%d%d", &n, &k); std::queue<int> win_qu; // 勝ち先 std::vector<std::vector<int>> count(n); // 禁止数字勝ち std::vector<int> win(n, -1); // (0, 1, 2) := (lose, win, pro) for(int i = n - 1; i >= 0; i--) { while (!win_qu.empty() and win_qu.front() > i + k) { win_qu.pop(); } int win_cnt = win_qu.size() + count[i].size(); if (win_cnt == 0) { win[i] = 0; win_qu.push(i); } else if (win_cnt == 1) { int add = (win_qu.empty() ? count[i][0] : win_qu.front()) - i; win[i] = 2; if(i - add >= 0) count[i - add].push_back(i); } else if (win_cnt >= 2) { win[i] = 1; } } std::vector<int> ans; for (int i = 1; i <= k; i++) if (win[i] == 0) ans.push_back(i); for (int i: count[0]) ans.push_back(i); sort(begin(ans), end(ans)); if (ans.empty()) ans.push_back(0); for (int v: ans) printf("%d\n", v); return 0; }