結果
問題 |
No.3166 [Cherry 7th Tune *] 桜の守人
|
ユーザー |
|
提出日時 | 2025-05-31 15:34:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 1,289 bytes |
コンパイル時間 | 1,113 ms |
コンパイル使用メモリ | 110,784 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-05-31 15:34:03 |
合計ジャッジ時間 | 3,282 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <iostream> #include <cstdint> #include <vector> #include <deque> #include <algorithm> using namespace std; static inline bool check(const uint32_t N, const uint32_t L, const uint32_t K, const vector<uint32_t>& X, const uint32_t P) noexcept { deque<uint32_t> guardians; for (uint32_t i = 0; i != N; ++i) guardians.push_back(X[i] + P * 2); while (!guardians.empty() && guardians.front() < L) guardians.pop_front(); if (guardians.size() < K) return false; for (uint32_t i = 0; i != N;) { if (guardians.front() < X[i] + L) guardians.pop_front(); else guardians.push_back(X[i] + L + P * 2), ++i; if (guardians.size() < K) return false; } return true; } static inline uint32_t solve(const uint32_t N, const uint32_t L, const uint32_t K, const vector<uint32_t>& X) noexcept { uint32_t l = 0, r = 1'000'000'000; while (l + 1 < r) { const uint32_t c = (l + r) >> 1; if (check(N, L, K, X, c)) r = c; else l = c; } return r; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); uint32_t T, i; cin >> T; for (i = 0; i != T; ++i) { uint32_t N, L, K, i; cin >> N >> L >> K; vector<uint32_t> X(N); for (i = 0; i != N; ++i) cin >> X[i]; sort(X.begin(), X.end()); cout << solve(N, L, K, X) << '\n'; } return 0; }