Submission #1179660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179660		niepamietamhasla	Room Temperature (JOI24_ho_t1)	C++20	100 / 100	103 ms	4612 KiB

Main

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

vector<ll> ai;
multiset<ll> usuniete;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, t;
    cin >> n >> t;
    ll x;
    for(int i = 0; i < n; ++i){
        cin >> x;
        ai.push_back(x);
    }
    sort(ai.begin(),ai.end());
    for(int i = 1; i < n; ++i){
        ai[i] = ai[i] - (ai[i] - ai[0]) / t * t;
    }
    sort(ai.begin(),ai.end());
    ll w = 1e9;
    ll minv = 1e9;
    for(int i = n - 1; i >= 0; --i){
        if(i > 0){
            ai[i] = ai[i] - (ai[i] - ai[i-1]) / t * t;
        }
        while(usuniete.size() > 0){
            auto it = usuniete.end();
            --it;
            if((*it) > ai[i]){
                ll v = (*it);
                usuniete.erase(it);
                v -= t;
                minv = min(minv, v);
            }
            else{
                break;
            }
        }
        w = min(w, ((abs(ai[i] - min(ai[0], minv))) + 1) / 2);
        int p = (ai[i] - ai[0]) / t;
        p = (ai[i]) - p * t;
        usuniete.insert(p);
    }
    // int val = ai[0] - t;
    // cout << val << " v\n";
    // while(usuniete.size() > 0){
    //     auto it = usuniete.end();
    //     --it;
    //     if((*it) > val){
    //         ll v = (*it);
    //         usuniete.erase(it);
    //         v -= t;
    //         minv = min(minv, v);
    //     }
    //     else{
    //         break;
    //     }
    // }
    // w = min(w, ((abs(val - minv)) + 1) / 2);
    cout << w << "\n";
    return 0;
}

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