結果
問題 |
No.3221 Count Turns
|
ユーザー |
|
提出日時 | 2025-08-01 22:35:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 844 bytes |
コンパイル時間 | 1,999 ms |
コンパイル使用メモリ | 204,844 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-01 22:35:47 |
合計ジャッジ時間 | 5,684 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main () { int N; cin >> N; ll H, T; cin >> H >> T; std::vector<ll> A(N), D(N); for (ll& a : A) cin >> a; for (int i = 0; i < N; i ++) { D[i] = (H - 1) / A[i] + 1; } ll ok = H * T, ng = 0; while (abs(ok - ng) > 1) { ll mu = (ok + ng) / 2; ll s = 0; for (ll d : D) { s += mu / d; } (s >= T ? ok : ng) = mu; } vector<ll> C(N, 0); vector<int> ids; for (int i = 0; i < N; i ++) { C[i] = (ok - 1) / D[i]; if (ok % D[i] == 0) { ids.push_back(i); } } T -= accumulate(C.begin(), C.end(), 0ll); sort(ids.begin(), ids.end(), [&](int i, int j) { ll a = A[i] * D[i], b = A[j] * D[j]; if (a != b) return a > b; else return i < j; }); for (int i = 0; i < T; i ++) { C[ids[i]] ++; } for (auto& a : C) cout << a << " "; cout << endl; }