結果
問題 |
No.3221 Count Turns
|
ユーザー |
|
提出日時 | 2025-08-01 23:12:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 1,540 bytes |
コンパイル時間 | 817 ms |
コンパイル使用メモリ | 107,048 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-01 23:12:27 |
合計ジャッジ時間 | 3,959 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <iostream> #include <cstdint> #include <vector> #include <algorithm> static inline constexpr std::vector<uint_fast32_t> solve(const uint_fast32_t N, const uint_fast32_t H, const uint_fast32_t T, const std::vector<uint_fast32_t>& A) noexcept { uint_fast64_t l = 0, r = 10'000'000'000'000; while (l + 1 < r) { const uint_fast64_t c = (l + r) / 2; uint_fast64_t count_operation = 0; for (uint_fast32_t i = 0; i != N; ++i) count_operation += c / ((H + A[i] - 1) / A[i]); if (count_operation >= T) r = c; else l = c; } std::vector<uint_fast32_t> ans(N, 0); uint_fast32_t count_operation = 0; for (uint_fast32_t i = 0; i != N; ++i) count_operation += (ans[i] = l / ((H + A[i] - 1) / A[i])); std::vector<std::pair<uint_fast64_t, uint_fast32_t>> rest(N); for (uint_fast32_t i = 0; i != N && count_operation < T; ++i) rest[i] = { ~(A[i] * static_cast<uint_fast64_t>(l % ((H + A[i] - 1) / A[i]) + 1)), i }; std::sort(rest.begin(), rest.end()); for (uint_fast32_t i = 0; i != T - count_operation; ++i) ++ans[rest[i].second]; return ans; } static inline void output(const uint_fast32_t N, const std::vector<uint_fast32_t>& ans) noexcept { std::cout << ans[0]; for (uint_fast32_t i = 1; i != N; ++i) std::cout << ' ' << ans[i]; std::cout << '\n'; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast32_t N, H, T, i; std::cin >> N >> H >> T; std::vector<uint_fast32_t> A(N); for (i = 0; i != N; ++i) std::cin >> A[i]; output(N, solve(N, H, T, A)); return 0; }