Submission #1208934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208934		qilby	Room Temperature (JOI24_ho_t1)	C++20	5 / 100	1 ms	328 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 500009;

ll n, t, a[N], p[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> t;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) a[i] %= t;
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i];

    ll res = (ll)1e18;

    for (int i = 1; i <= n; i++) {
        ll x = a[i];

        int l = 1, r = i;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (abs(a[mid] - x) <= t - abs(a[mid] - x)) r = mid;
            else l = mid + 1;
        }

        int lg = l;

        l = i, r = n;

        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (abs(a[mid] - x) <= t - abs(a[mid] - x)) l = mid;
            else r = mid - 1;
        }

        int rg = l;

        ll crr = x * (ll)(i - lg + 1) - (p[i] - p[lg - 1]);
        crr += t * (ll)(lg - 1) - x * (ll)(lg - 1) + p[lg - 1];

        crr += (p[rg] - p[i]) - x * (ll)(rg - i);
        crr += t * (ll)(n - rg) - (p[n] - p[rg]) + x * (ll)(n - rg);

        res = min(res, crr);
    }

    cout << res;
}

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