結果

問題 No.3166 [Cherry 7th Tune *] 桜の守人
ユーザー ymm-knight
提出日時 2025-06-16 18:31:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 463 ms / 2,000 ms
コード長 1,333 bytes
コンパイル時間 2,139 ms
コンパイル使用メモリ 206,136 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-16 18:31:51
合計ジャッジ時間 12,553 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define Loop(x,l,r) for (ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = ll(r)-1; x >= ll(l); --x)
#define Looc(x,l,r) for (ll x = ll(l); x <= ll(r); ++x)
#define LoocR(x,l,r) for (ll x = ll(r); x >= ll(l); --x)
#define int ll
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#ifndef DB
#define DB 0
#define endl '\n'
#endif
#define debugl(l) if constexpr ((l) < DB)
#define debug debugl(0)

void solve()
{
	int n, k;
	ll len;
	cin >> n >> len >> k;
	vector<ll> pos(n);
	for (auto &x : pos)
		cin >> x;

	auto can = [&](ll go) {
		if (go >= 2*len)
			return true;
		map<ll, ll> ps;
		for (auto p : pos) {
			auto lf = p - go;
			auto ri = p + go;
			if (lf < 0) {
				ps[lf + len] += 1;
				//ps[len] -= 1;
				ps[0] += 1;
				ps[ri] -= 1;
			} else if (ri >= len) {
				ps[lf] += 1;
				//ps[len] -= 1;
				ps[0] += 1;
				ps[ri - len] -= 1;
			} else {
				ps[lf] += 1;
				ps[ri] -= 1;
			}
		}
		ll sum = 0;
		for (auto [x, y] : ps) {
			sum += y;
			if (sum < k)
				return false;
		}
		return true;
	};

	ll l = 0, r = len;
	while (l < r) {
		ll mid = (l+r)/2;
		if (can(mid))
			r = mid;
		else
			l = mid+1;
	}
	cout << l << '\n';
}

signed main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int t = 1;
	cin >> t;
	while (t--)
		solve();
}
0