結果

問題 No.3166 [Cherry 7th Tune *] 桜の守人
ユーザー 矢澤式WINTER
提出日時 2025-05-30 22:29:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 9,260 bytes
コンパイル時間 6,182 ms
コンパイル使用メモリ 336,312 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-30 22:29:51
合計ジャッジ時間 16,655 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
/*
 winter's kyopro template 
*/
//*/
#include <atcoder/all>
using namespace atcoder;
//*/
 
 
//                                  ......Jgg+.
//                            ..jQHHMHHHHMMHHMNHHmaJ+&&ga&&J-....          ..(-.
//                         .JdMHMM@@@@@MMHyyyWHHWMHHMMM@MMMHHHMMMNmmm&-..&HMMMMMm.
//                       .(WHM@@@@@@@@MMWyyWWWH@@@@@g@@@@@MH@@@@@@@@MMHMMMHVyyVHMNHHHm.
//                      .dMM@@@@@@@@@MHVWWWMMM@@@@@@@@@@@@@@@@@@@@@@@@@@@MkWWWHHHWyyHMn.
//                     .dH@@@@MMMMHHHWWHWH@@@@@@@@@@@g@@@@g@@@@@@@@@@@@@@@MMHyyyyyyyWHMNma..
//                    (WH@@@@NWyyyWWHUuuuXWH@@@@@@@@@@@g@@@@@@M@@@@@@g@@@@@HHkyyyyyVH@@@MMHNm,
//                   (WH@@@@@@HyyWHUuuuuuuuuXWHHHH@@@@@@@g@@@@@MM@@@@@@@@@@HUWkyyyyWM@@@@@@MMNm-
//                  .dH@@@@@@@MkWHkkkkkkXuuuuuuuuXWUWHHHHHHHg@@g@MHHg@@HHHUuuuWkyyyyWM@@@@@@@MMH+
//                 .dMM@@@g@@MHHM@@@@@@@HHkkkXuuuWSuuuuuuuuuuuuXXXUHkXuuuuuuuuXHkyyyyWHM@@@@@@MHNe.
//                 (MM@@@@@@@NW@@@@@@MM@@@@@@@HHWHkkXuuuuuuuuuuuuuuuUHkuuuuuuuuXHWyyyyyVHM@@@g@@MNl
//                .WH@@@@@@@@@M@@@@@MM@@@@@@@M9=d@@@@gHHHHkkkkkkQQQQQkHkQkkHHHkkWkyyyyyyyWH@@@@@MHH-
//               .dH@@@@@g@@@H@@@@@MM@@@@@@H9! (W@@@@@@@@MM@@@@@@@@@@@@MM@@@@@@@@HVyyyyyWWW@@@@@@MNr
//               (HM@@@@@@@@MM@@@@@M@g@@@@B:``.(@@@@@@@@@MH@@@@@@@@@@@@@MM@@@@@@@MHWWkWqH@@@@@@@@MHH_
//              .dHM@@@@g@@@H@@@@@H@@@@@M3_`.` J@@@@@@@@@H?H@@@@@@@@@@@@@HM@@@g@@@@HHWyyVH@@@@@@@@HH~
//              dMM@@@@@@@@HM@@@@@H@@g@#>..... dM@@@g@@@@D.?H@@@@@g@@g@@@@M@@@@@@@@HVWWWH@@@@@g@@@HN-
//            .dMM@@@@g@@gMH@@@@@M@@@@#><?zw&. j@@@@@@g@M>` ?M@@@@@@@@@@@@H@@@@@@@@MH@M@@@@@@@@@@@HM{
//           .dMM@@@@@@@@@M@@@@g@H@@@#!```` _?IjH@@@@@@M$_``.?H@@@@@@g@@@@M@@@g@@@@M@@@@@@@@@@@@@@HM>
//        ..jHH@@@@@g@@g@MM@@@@@@HM@MC......`.`_W@@@@@@D_..-J+dMMM@MM@@@g@H@@@@@@@MH@@@@@@@@@g@@@MHD`
//  .gHHQHMMM@@@@@@@@@@MHM@@@@g@@HM@D~.(ggNQma,.jH@MM@#~.-~~_.. ?WMMHM@@@@H@@@@g@@HHM@@@@@g@@@g@@MMD
//   ZMHM@@@@@@@@@@@@@MHM@@@@@@@MHMMI+MB=?HNHHMn-U@MMM{.````.``.. ?TMMM@@@M@g@@@@@H@H@@@g@@@@@@@@HM$
//    ?WMHMHM@@@@@@g@MM@@@Nc?H@MHMMNd#:+-.dMMNZ>.(WN?U:`.`.``.```.`._!_TMM@@@@g@@MM@MM@@@@@g@@@@@H#:
//    .+MHM@@@@@@@@@MM@@@@@No(HHHVUWN{(MMMMMMMb_`.-?!`.`...-((-..`.`.`. (M@@@@@@@H@@M#M@@@@@g@@@MHR
//   (dMM@@@@@@@@@MHMHWHM@@M81zHD_dMN<(MMMMMMMD_``.``.`. (JgggJ.<!.``. (H@@@g@@@M@@@MMH@@g@@@@@@MHR
//  +MM@@@@@@@@MMHHM@Nm._79!<-(>`(wI?3-?MHWWM@!.`.`.`.`.(TYYYHMMNe..`.(H@@@@@@MHM@@MM@@@@@@@@g@@MHR
// jMHMMM@@@@MMM@@HM@@@@H+ <i(w> jK>:~~__<?7!_``.`.`.`.``.``.` _7MMs(d@@@@@@@MWM@@MHM@@@@@@@g@@@MHD
// dHH#M@@@MMM9>?WH@@@MM@N;. ~!.jMH<:::::_`.``.`..`.``.`.`.`...  .(WHMM@@@@HY! dHHHHM@@@@@g@@@@@MMr
// dHHM@@@MM9!   dHM@MHM@#Nx `` ?MN<_____.`.`......`.``.`.`._~:::((ud@@HH9=``` jH@HH@@@@@@@@@@@@MMR.
// vMHM@MH#>     dMM@HHHMMHM2 `.`?MN, ````.`..jUwz?>++. ``.`_~~:?TY9Y=<~_``...dM9TMH@@M@@@@g@@g@@HH_
//  OMM@H#:      .WMHHH@@MMHN;.`.`_TMm. `.```.jZ=====zw:.``.`..`````..-JJJggHHY! .HH@MHM@@@@@@@@@HN{
//  .dHMHR        _WMHHMC!?TMN+.`.`._vHW&...``.?====zz>_`.`.``````..JdMBYTY^`    .WH@HHMM@@@g@MM@MMR.
//   (MMHR_         _7T=`   (MN+``.` (wXWUUO+-.. _~<<`.`.`..` .-JgHMHHH,          dMM@HHHM@@@@@MHMHNe.
//    (TH9!                  (HNx..`.wdyykX<(HWH4Z1++(((JJ&zwXWWWHHWWXMNo          TMH@MHH@@@@@HHHH#MH+
//                            (WMm&(wwXyyyXXdkW0`.`.`. dWyR+uwyyyyyyyWwHN{          ?THMMH@@@@@HMY7TMHC
//                             jMSXSwyyyyyyWXUWH......(dHWUXXyyyyyyyyykXMHe.            dMM@@@MH#~
//                             dMHXXyyyyyyyWWyXkwXZuuuwXwuUyyyyyyyyyyykwvdMm.           J@M@@@MMD`
//                             (TMM@HHQQkkkWHyyyyyyyyyy0<:;zyyyyyyyyyXXf~_WN-          .dH@@@HM@!
//                                `??TYYYWHMMWyyyyyyyyyWA&uwyyWHkyyyUwVC((dMMMH_       .HH@@MM8!
//                                         vMNWyyyyyyyyyyyyyyyyyWHkQHmdWWyyWHMD`      .dMMMM#=`
//                                          7MMkyyyyyyyyyyyyyyyyyWWHMMkWWWWMMHH+      JMMM9=`
//                                           (TMMHkWyyyyyyyyyyyyyWHWkWH9Y<zUV<WN;      ?!`
//                                            .(d@HMHWkkWyyyyyyyVWHHM8w+ ` _.(HNo.
//                                       .(gkHHMMMMNWyyWWWWVyyypHpW0z;<zO++zV9?WN;
//                                      (WMM9UOOTUv?WWkWVVVWWWWU0CzXz;;;;;;+Z:-dM{
//                                      (MR~1+-<.(w++<?TH9TC1<;;;;;?1;;>;;+v:(dMD`
//                                       ?MH+?1-.._<zz;vC;;;;>++;;>;>;;;;+wC<&dN:
//                                       `(M#!_?u-..(z&++>;;<jV<;>;;;>>>+jZ~(dM=
//                                        .TMm+JZ1--_._~?zz&u9Twzz&&zZ77<!(WMB^
//                                          (WHB1-_(z_..(-____..~_~~_.._-JW#>
//                                        .gHMB! <<.(1(JXQe+((+<<<1+(+1WMMY`
//                                      .dM9!_~```-?1-.(dMD<<<<<(-....dMC
//                                     (W#! ````````` (dH@~````` _?<.dM=
//                                    (H8`````````  .(HHM}` `````` (WB!
//                                   .d#:`` ````  .JHMHM#~``` `` .(M9!
//                                  `(MD ` ````.JkM9=`(H$``````  jM$
//                                   (@{``` ` (HB>`   (@l ` `` `.WK~
//                                  .dMx  ``.jM3`     JM{``` ```.MK`
//                                  .WHHA<+(dMC       dM>````` `(M$
//                                   dHH$_(WM3        dN: ``` ` dN{
//                                   ?MHmJdH#!       .d#~` ````-WD`
//                                     ?TTB9!        (Mb- ` ` .dM>
//                                                 .dH9!(A-. .dM%
//                                                (MNI-.dWyVQd#>
//                                                .TMm+?UVWWM#>
//                                                  ?WMHmdMM9!
//                                                    _?7T=!
 
 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define ALL(x) (x).begin(),(x).end()
#define dbgv(x); for(auto now : x) cout << now << " "; cout << endl;
//using P = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//*/
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vint;
random_device rnd;
mt19937 rng(rnd());

template<typename T=int>
struct CC {
  bool initialized;
  vector<T> xs;
  CC(): initialized(false) {}
  void add(T x) { xs.push_back(x);}
  void init() {
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    initialized = true;
  }
  int operator()(T x) {
    if (!initialized) init();
    return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
  }
  T operator[](int i) {
    if (!initialized) init();
    return xs[i];
  }
  int size() {
    if (!initialized) init();
    return xs.size();
  }
};

void solve(){
  int n,l,k; cin >> n >> l >> k;
  vll x(n); rep(i,n) cin >> x[i];
  ll ac = l/2,wa = 0;
  while(ac-wa > 1){
    ll mid = (ac+wa)/2;
    CC cc;
    rep(i,n){
      cc.add(x[i]);
      cc.add((x[i]+mid)%l);
      cc.add((x[i]-mid+l)%l);
    }
    cc.add(l-1);
    cc.init();
    vint sums(cc.size()+1,0);
    int sz = cc.size();
    vector<pair<int,int> > event;
    int mn,mx;
    rep(i,n){
      int ll = cc((x[i]-mid+l)%l);
      int r = cc((x[i]+mid)%l);
      //cerr << ll << " " << r << endl;
      if(ll <= r){
        event.push_back(make_pair(ll,-1));
        event.push_back(make_pair(r,1));
        chmin(mn,ll);
        chmax(mx,r);
        //if(mid == 150) cerr << ll << " " << r << endl;
      }else{
        event.push_back(make_pair(ll,-1));
        event.push_back(make_pair(sz-1,1));
        event.push_back(make_pair(0,-1));
        event.push_back(make_pair(r,1));
        chmin(mn,ll);
        chmax(mx,r);
        chmin(mn,0);
        chmax(mx,sz-1);
        //if(mid == 150) cerr << ll << " " << sz-1 << endl;
        //if(mid == 150) cerr << 0 << " " << r << endl;
        //cerr << ll << " " << sz << " " << 0 << " "<< r << endl;
      }
    }
    int cnt = 0;
    sort(ALL(event));
    bool ok = true;
    ///cerr << "now = " << mid << " ";
    rep(i,event.size()){
      auto [key,val] = event[i];
      if(key == cc(l-1)) break;
      cnt -= val;
      while(i+1 < event.size() && event[i+1].first == key){
        i++;
        auto [key2,val2] = event[i];
        cnt -= val2;
      }
      //cerr << cnt << " ";
      if(cnt < k && i != event.size() -1) ok = false;
    }
    if(cnt < k) ok = false;
    //cerr << endl;
    //cerr << mn << " " << mx << endl;
    //if(mn != 0 || mx != sz-1) ok = false;
    if(ok || 2*mid >= l) ac = mid;
    else wa = mid;
  }
  cout << ac << "\n";
} 
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1; cin >> t;
  rep(testcase,t) solve();
}
0