結果
問題 | No.78 クジ付きアイスバー |
ユーザー |
![]() |
提出日時 | 2019-02-09 01:09:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,339 bytes |
コンパイル時間 | 692 ms |
コンパイル使用メモリ | 74,432 KB |
最終ジャッジ日時 | 2025-01-06 21:04:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 WA * 14 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:12:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 12 | scanf("%zu %jd %s", &N, &K, buf); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <cstdint> #include <vector> #include <set> #include <map> #include <string> int main() { size_t N; intmax_t K; char buf[64]; scanf("%zu %jd %s", &N, &K, buf); std::string S = buf; std::vector<intmax_t> atari(N); for (size_t i = 0; i < N; ++i) atari[i] = S[i]-'0'; if (S == std::string(N, '0')) return !printf("%jd\n", K); std::vector<intmax_t> tada(N); for (size_t i = 0; i < N; ++i) { int cur = 1; tada[i] = 0; for (size_t j = i; cur && tada[i] <= intmax_t(N);) { ++tada[i]; cur += atari[j] - 1; ++j %= N; } } intmax_t res = 0; std::map<intmax_t, intmax_t> seen; intmax_t last = 0; intmax_t ice = 0; while (true) { ++res; ice += tada[last]; if (tada[last] > intmax_t(N)) return !printf("%jd\n", res); if (ice >= K) return !printf("%jd\n", res); intmax_t next = (last + tada[last]) % N; seen.emplace(last, next); last = next; if (seen.count(last)) break; } intmax_t unit = 0; intmax_t period = 0; intmax_t cur = last; do { unit += tada[cur]; ++period; } while (cur != last); res += (K - ice) / unit * period; ice += (K - ice) / unit * unit; while (ice < K) { ++res; ice += tada[last]; last = (last + tada[last]) % N; } printf("%jd\n", res); }