제출 #1341089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1341089		joacru	Room Temperature (JOI24_ho_t1)	C++20	85 / 100	2092 ms	18892 KiB

Main

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

#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, t;
    cin>>n>>t;
    
    vector<int> a(n);
    for(int &x: a){
        cin>>x;
        x%=t;
    }
    
    int l = -1, r = t / 2;
    vector<pair<int,int>> es;

    while(r-l>1){
        es.resize(0);
        int m=(l+r)/2;
        for(int x: a){
            es.push_back({x-m,+1});
            es.push_back({x+m+1,-1});
            es.push_back({x-m+t,+1});
            es.push_back({x+m+t+1,-1});
        }
        sort(ALL(es));
        int cnt = 0;
        bool valid = 0;
        for(int i = 0; i < (int)es.size(); ++i){
            int x = es[i].first;
            while(i<(int)es.size()&&es[i].first == x){
                cnt += es[i].second;
                ++i;
            }
            --i;
            if(cnt >= n){
                valid = 1;
                break;
            }
        }
        if(valid) r = m;
        else l = m;
    }

    cout<<r<<"\n";

    return 0;
}

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