結果
問題 |
No.3166 [Cherry 7th Tune *] 桜の守人
|
ユーザー |
|
提出日時 | 2025-05-31 11:37:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 1,177 bytes |
コンパイル時間 | 1,966 ms |
コンパイル使用メモリ | 201,260 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-31 11:37:55 |
合計ジャッジ時間 | 5,661 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:60:54: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 60 | for (int i = 1; i < n + 1; i++) scanf("%d", w + i); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef unsigned long long ull; const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f; ll res; int n, m, cnt, w[N]; int k; bool check(int mid) { priority_queue<int, vector<int>, greater<int> > q, q2; for (int i = 1; i < n + 1; i++) if (w[i] <= mid) q.push(w[i]); else if (m - w[i] <= mid) q.push(w[i] - m); else q2.push(w[i]); if (q.size() < k) return 0; while (q.size()) { auto u = q.top(); q.pop(); q2.push(u + m); int ne = u + mid + 1; if (ne >= m) break; while (q.size() && q.top() == u) { q.pop(); q2.push(u + m); } while (q2.size() && q2.top() - (ne - 1) <= mid) { if (ne - q2.top() <= mid) { q.push(q2.top()); q2.pop(); } else { q2.push(q2.top() + m); q2.pop(); } } if (q.size() < k) return 0; } return 1; } void solve() { int l = 0, r = m; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%d\n", l); } int main() { int T; cin >> T; while (T--) { cin >> n >> m >> k; for (int i = 1; i < n + 1; i++) scanf("%d", w + i); solve(); } return 0; }