結果
問題 | No.2627 Unnatural Pitch |
ユーザー |
|
提出日時 | 2024-02-09 21:50:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 112 ms / 4,000 ms |
コード長 | 1,521 bytes |
コンパイル時間 | 1,482 ms |
コンパイル使用メモリ | 176,956 KB |
実行使用メモリ | 16,444 KB |
最終ジャッジ日時 | 2024-09-28 15:05:38 |
合計ジャッジ時間 | 3,777 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define all(x) x.begin(), x.end()#define app push_back#ifdef LOCAL#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << '\n';}(#__VA_ARGS__, ":", __VA_ARGS__)#else#define debug(...)#endifconst int inf=1e18;const int maxn=2e5+5;vector<int> inter[maxn];int32_t main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,k,l,u;cin>>n>>k>>l>>u;int a[n];for(int i=0;i<n;++i) cin>>a[i]; sort(a,a+n);int low=(-inf);int up=inf;while(up-low>1){int mid=(low+up)/2;int c1=0,c2=0;for(int i=0;i<n;++i){if(a[i]+mid>=u-k+1) {++c2;}else if(a[i]+mid<=l-1) {++c1;}}if(c2>=c1) up=mid;else low=mid;}auto f=[&](int x)->int{if(x<l) {return (l-x+k-1)/k;}else if(x>u) {return (x-u+k-1)/k;}return 0;};int x=up;debug(x);for(int i=0;i<n;++i) {a[i]+=x;}int cur=0;for(int i=0;i<n;++i) {cur+=f(a[i]);}int res=cur;for(int i=0;i<n;++i){inter[((l-a[i])%k+k)%k].app(i);inter[((u+1-a[i])%k+k)%k].app(i);}for(int i=0;i<k;++i) {sort(all(inter[i]));inter[i].erase(unique(all(inter[i])),inter[i].end());}for(int i=1;i<k;++i){for(int id:inter[i]){debug(i,id);cur-=f(a[id]+i-1);cur+=f(a[id]+i);}res=min(res,cur);}cout<<res;return 0;}