Submission #1266852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266852		Math4Life2020	Room Temperature (JOI24_ho_t1)	C++20	100 / 100	111 ms	24024 KiB

Main

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

const ll Nm = (1LL<<20); const ll E = 20;
ll pfs[Nm];
ll ipfs[Nm];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,T; cin >> N >> T;
    vector<ll> v0;
    for (ll i=0;i<N;i++) {
        ll a; cin >> a;
        a = a%T;
        v0.push_back(a);
        v0.push_back(a+T);
    }
    sort(v0.begin(),v0.end());
    for (ll i=0;i<(2*N);i++) {
        ipfs[i]=v0[i];
        //cout << v0[i] <<"\n";
    }
    pfs[0]=0;
    for (ll i=0;i<(2*N);i++) {
        pfs[i+1]=pfs[i]+ipfs[i];
    }
    ll ans = 8e18;
    ll m = N/2; //median index
    //i,i+1,i+2,...,i+m BELOW/AT
    //i+m+1,i+m+2,...,i+N-1
    for (ll i=0;i<=N;i++) {
        // ll sum1 = pfs[i+m+1]-pfs[i];
        // ll sum2 = pfs[i+N]-pfs[i+m+1];
        // ll aval = (ipfs[i+m]*(m+1)-sum1)+(sum2-ipfs[i+m]*(N-m-1));
        // ans = min(ans,aval);
        ans = min(ans,(v0[i+N-1]-v0[i]+1)/2);
    }
    cout << ans << "\n";
}

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