제출 #1333152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333152		prunjuice	Room Temperature (JOI24_ho_t1)	C++20	35 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N;
ll T;
vector<ll> A;

bool ok(ll D) {
    if (D >= T) return true;

    ll L = 0, R = T-1;
    bool split = false;
    ll L2 = -1, R2 = -1;

    for (ll a : A) {
        ll r = a % T;

        ll l = r - D;
        ll r2 = r + D;

        if (l < 0 || r2 >= T) {
            ll nl = (l + T) % T;
            ll nr = (r2) % T;

            if (!split) {
                split = true;
                L2 = nl;
                R2 = T-1;
                L = 0;
                R = nr;
            } else {
                ll nL = max(L, 0LL);
                ll nR = min(R, nr);
                ll nL2 = max(L2, nl);
                ll nR2 = min(R2, T-1);

                L = nL;
                R = nR;
                L2 = nL2;
                R2 = nR2;
            }
        } else {
            if (!split) {
                L = max(L, l);
                R = min(R, r2);
            } else {
                L = max(L, l);
                R = min(R, r2);
                L2 = max(L2, l);
                R2 = min(R2, r2);
            }
        }
    }

    if (!split) return L <= R;
    return (L <= R) || (L2 <= R2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> T;
    A.resize(N);

    for (int i = 0; i < N; i++) cin >> A[i];

    ll lo = 0, hi = 1e18;

    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }

    cout << lo << "\n";
}

• Subtask 1: 0 / 15
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 15