Submission #1231931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231931		clemmy14	Room Temperature (JOI24_ho_t1)	C++20	50 / 100	1 ms	328 KiB

Main

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

signed main() {
    int n, t; cin >> n >> t;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<n; i++) a[i]%=t;
    sort(a.begin(), a.end());
    vector<int> cur={a[0]};
    for(int i=1; i<n; i++) if(a[i] != a[i-1]) cur.push_back(a[i]);
    a=cur;
    vector<int> aa;
    for(int i=0; i<a.size(); i++) aa.push_back(a[i]-t);
    for(int i=0; i<a.size(); i++) aa.push_back(a[i]);
    for(int i=0; i<a.size(); i++) aa.push_back(a[i]+t);

    // for(auto x : aa) cout << x << ' ';
    // cout << endl;

    int best=t/2, half=t/2;

    for(int i=0; i<a.size(); i++) {
        auto prev = lower_bound(aa.begin(), aa.end(), a[i]-half), aft = upper_bound(aa.begin(), aa.end(), a[i]+half);
        aft--;
        best=min(best, max(a[i]-aa[prev-aa.begin()], aa[aft-aa.begin()]-a[i]));
    }
    
    //cout << best << endl;

    a.push_back(a[0]+t);

    // for(auto x : a) cout << x << ' ';
    // cout << endl;

    // cout << half << endl;

    for(int i=1; i<a.size(); i++) {
        int mid1 = (a[i]-a[i-1])/2 + a[i-1], mid2=(a[i]-a[i-1]+1)/2 + a[i-1];

        //cout << mid1 << ' ' << mid2 << endl;


        auto prev = lower_bound(aa.begin(), aa.end(), mid1-half), aft = upper_bound(aa.begin(), aa.end(), mid1+half); 
        aft--;
        best=min(best, max(mid1-aa[prev-aa.begin()], aa[aft-aa.begin()]-mid1));
        prev = lower_bound(aa.begin(), aa.end(), mid2-half); aft = upper_bound(aa.begin(), aa.end(), mid2+half);
        aft--;
        best=min(best, max(mid2-aa[prev-aa.begin()], aa[aft-aa.begin()]-mid2));
    }

    cout << best;

    return 0;
}

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