結果

問題 No.3166 [Cherry 7th Tune *] 桜の守人
コンテスト
ユーザー elphe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0