Submission #1309180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309180		IUA_Hasin	Room Temperature (JOI24_ho_t1)	C++20	100 / 100	71 ms	4428 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * JOI 2024 Final Round - Problem A: Room Temperature
 * The problem asks to minimize the maximum discomfort index.
 * Discomfort is distance to the set {Ai - k*T | k >= 0}.
 * This is minimized by treating Ai modulo T as points on a circle.
 */

int main() {
    // Optimize standard I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long t_val;
    if (!(cin >> n >> t_val)) return 0;

    // We only care about the remainder of appropriate temperatures modulo T
    vector<long long> b(n);
    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;
        b[i] = a % t_val;
    }

    // Sort the points to easily find gaps between them
    sort(b.begin(), b.end());

    long long max_gap = 0;

    // Calculate gaps between adjacent points
    for (int i = 0; i < n - 1; ++i) {
        max_gap = max(max_gap, b[i + 1] - b[i]);
    }

    // Calculate the "wrap-around" gap between the last and first points
    // This is the distance from the largest value back to the smallest through the boundary T
    max_gap = max(max_gap, t_val - (b.back() - b.front()));

    // The minimum window covering all points on the circle is (T - largest gap).
    long long d = t_val - max_gap;

    // The minimum unpleasantness U is the radius needed to cover that window.
    // U = ceil(d / 2). Since we are using integer division:
    long long ans = (d + 1) / 2;

    cout << ans << endl;

    return 0;
}

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