結果
問題 |
No.3166 [Cherry 7th Tune *] 桜の守人
|
ユーザー |
|
提出日時 | 2025-06-21 14:22:38 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,834 bytes |
コンパイル時間 | 553 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 294,028 KB |
最終ジャッジ日時 | 2025-06-21 14:23:37 |
合計ジャッジ時間 | 56,302 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | WA * 10 TLE * 16 |
ソースコード
## https://yukicoder.me/problems/no/3166 def solve2(N, L, K, X, p): if 2 * p >= L: return True # 座標圧縮 x_set = {0, L, 2 * L} for x in X: p1 = x - p p2 = x + p x_set.add(p1) x_set.add(x) x_set.add(p2) x_set.add(p1 + L) x_set.add(x + L) x_set.add(p2 + L) x_set.add(p1 + 2 * L) x_set.add(x + 2 * L) x_set.add(p2 + 2 * L) x_list = list(x_set) x_list.sort() x_map = {} for i, x in enumerate(x_list): x_map[x] = i x_len = len(x_list) # 円周を加味したimos法 array = [0] * (3 * x_len + 1) for x in X: p1 = x - p p2 = x + p for j in (L, 2 * L): y1 = x_map[(p1 + j)] y2 = x_map[(p2 + j)] array[y1] += 1 array[y2] -= 1 z = 0 for i in range(3 * x_len + 1): z += array[i] array[i] = z j0 = x_map[L] j1 = x_map[2 * L] for j in range(j0, j1): if array[j] < K: return False return True def solve(N, L, K, X): x_list = [2 * x for x in X] low = 0 high = 2 * L while high - low > 1: mid = (high + low) // 2 if solve2(N, 2 * L, K, x_list, mid): high = mid else: low = mid if solve2(N, 2 * L, K, x_list, low): p = low else: p = high if p % 2 == 1: return (p // 2) + 1 else: return p // 2 def main(): T = int(input()) answers = [] for _ in range(T): N, L, K = map(int, input().split()) X = list(map(int, input().split())) ans = solve(N, L, K, X) answers.append(ans) for ans in answers: print(ans) if __name__ == "__main__": main()