結果

問題 No.3166 [Cherry 7th Tune *] 桜の守人
ユーザー tnakao0123
提出日時 2025-05-31 17:27:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 207 ms / 2,000 ms
コード長 1,869 bytes
コンパイル時間 670 ms
コンパイル使用メモリ 48,188 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-31 17:27:13
合計ジャッジ時間 6,826 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:70:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |   scanf("%d", &tn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:74:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   74 |     scanf("%d%d%d", &n, &l, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:75:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   75 |     for (int i = 0; i < n; i++) scanf("%d", xs + i);
      |                                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3166.cc:  No.3166 [Cherry 7th Tune *] 譯懊・螳井ｺｺ - yukicoder
 */

#include<cstdio>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 20000;
const int MAX_M = MAX_N * 2 + 2;

/* typedef */

/* global variables */

int xs[MAX_N];
int uxs[MAX_M], cs[MAX_M + 1];

/* subroutines */

bool check(int n, int l, int k, int p) {
  if (p * 2 >= l) return true;

  int m = 0;
  uxs[m++] = 0, uxs[m++] = l;
  for (int i = 0; i < n; i++) {
    int x0 = xs[i] - p, x1 = xs[i] + p;
    if (x0 < 0) x0 += l;
    if (x1 > l) x1 -= l;
    uxs[m++] = x0, uxs[m++] = x1;
  }
  sort(uxs, uxs + m);
  m = unique(uxs, uxs + m) - uxs;

  fill(cs, cs + m + 1, 0);
  for (int i = 0; i < n; i++) {
    int x0 = xs[i] - p, x1 = xs[i] + p;
    if (x0 < 0) {
      int j0 = lower_bound(uxs, uxs + m, x0 + l) - uxs;
      int j1 = lower_bound(uxs, uxs + m, x1) - uxs;
      cs[0]++, cs[j1]--, cs[j0]++, cs[m - 1]--;
    }
    else if (x1 > l) {
      int j0 = lower_bound(uxs, uxs + m, x0) - uxs;
      int j1 = lower_bound(uxs, uxs + m, x1 - l) - uxs;
      cs[0]++, cs[j1]--, cs[j0]++, cs[m - 1]--;
    }
    else {
      int j0 = lower_bound(uxs, uxs + m, x0) - uxs;
      int j1 = lower_bound(uxs, uxs + m, x1) - uxs;
      cs[j0]++, cs[j1]--;
    }
  }
  for (int i = 0; i < m; i++) cs[i + 1] += cs[i];

  //printf(" p=%d:", p);
  //for (int i = 0; i < m - 1; i++) printf(" %d", cs[i]); putchar('\n');
  
  return (*min_element(cs, cs + m - 1) >= k);
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n, l, k;
    scanf("%d%d%d", &n, &l, &k);
    for (int i = 0; i < n; i++) scanf("%d", xs + i);

    int p0 = 0, p1 = (l + 1) / 2;
    while (p0 + 1 < p1) {
      int p = (p0 + p1) / 2;
      if (check(n, l, k, p)) p1 = p;
      else p0 = p;
    }

    printf("%d\n", p1);
  }

  return 0;
}
0