結果
問題 |
No.3166 [Cherry 7th Tune *] 桜の守人
|
ユーザー |
![]() |
提出日時 | 2025-05-30 22:55:27 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 1,905 bytes |
コンパイル時間 | 3,650 ms |
コンパイル使用メモリ | 284,348 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-30 22:55:35 |
合計ジャッジ時間 | 7,647 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto& i:a) #define ff first #define ss second #define all(a) begin(a),end(a) #define allr(a) rbegin(a),rend(a) #define pb push_back using ll =long long; using pii=pair<int,int>; using pll=pair<ll,ll>; using vi=vector<int>; using vll=vector<ll>; template<class T> inline bool chmin(T& a,T b){return a>b?a=b,1:0;} template<class T> inline bool chmax(T& a,T b){return a<b?a=b,1:0;} const int INFI=numeric_limits<int>::max()/2; const ll INFL=numeric_limits<ll>::max()/2; ll n,l,k; vll x; void solve(){ sort(all(x)); auto f=[&](ll p)->bool { if(2*p>=l)return true; vector<ll> v; v.pb(0);v.pb(l-1);v.pb(l); rep(i,0,n){ ll L=(l+x[i]-p)%l; ll R=(L+2*p)%l; v.pb(L);v.pb(R); } sort(all(v));v.erase(unique(all(v)),end(v)); ll sz=v.size(); vll imos(sz); rep(i,0,n){ ll L=(l+x[i]-p)%l; ll R=(L+2*p)%l; ll Li=distance(begin(v),lower_bound(all(v),L)); ll Ri=distance(begin(v),lower_bound(all(v),R)); if(Li<Ri){ imos[Li]++;imos[Ri]--; }else{ imos[0]++;imos[Ri]--; imos[Li]++; } } rep(i,0,sz-1){ if(i!=0){ imos[i]+=imos[i-1]; } if(imos[i]<k)return false; } return true; }; ll ok=l,ng=0; while(abs(ok-ng)>1){ ll mid=(ok+ng)/2; if(f(mid))ok=mid; else ng=mid; } cout<<ok<<'\n'; } int main(){ cin.tie(0)->sync_with_stdio(0); int t;cin>>t; while(t--){ cin>>n>>l>>k; x.resize(n); rep(i,0,n)cin>>x[i]; solve(); } return 0; } /* */