| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1338289 | retarde | Room Temperature (JOI24_ho_t1) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;
bool ok(int n, int mid, int t, vi &a) {
vector<pii> rng; rng.reserve(3*n);
for (int i = 0; i < n; i++) {
if (2*mid+1 >= t) rng.pb({0, t-1});
else {
if (a[i] >= mid) {
rng.pb({a[i] - mid, a[i]});
} else {
rng.pb({0, a[i]});
rng.pb({t-(mid-a[i]), t-1});
}
if (a[i]+mid < t) {
rng.pb({a[i] + 1, a[i] + mid});
} else {
rng.pb({a[i] + 1, t-1});
rng.pb({0, a[i]+mid-(t-1)-1});
}
}
}
vector<pii> event; event.reserve(6*n);
for (auto &x : rng) {event.pb({x.fi, 1}); event.pb({x.se + 1, -1});}
sort(all(event));
int cur = 0;
for (auto &x : event) {
cur += x.se;
if (cur == n) return 1;
// for (auto &y : x.se) {if (y == -1) cur += y;}
}
return 0;
}
inline void solve() {
int n, t;
cin >> n >> t;
int ans = 0; vi a;
for (int i = 0; i < n; i++) {
int x; cin >> x;
a.pb(x%t);
}
sort(all(a));
int lo = -1; int hi = 1e9+5;
while (hi > lo + 1) {
int mid = (lo + hi) / 2;
if (ok(n, mid, t, a)) hi = mid;
else lo = mid;
}
cout << hi << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
//setIO();
int t = 1;
if (tc) {
cin >> t;
}
while (t--) {
solve();
}
}