Submission #1309028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309028		IUA_Hasin	Room Temperature (JOI24_ho_t1)	C++20	50 / 100	2 ms	580 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
 
#define ll                                  long long
#define ld                                  long double
#define endl                                "\n"
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define all(v)                              v.begin(), v.end()

using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;


const ll infp = 1e18;
const ll infn = 1e18 * (-1);

const ll N = 2e5 + 10;
const ll M = 5e3 + 10;
const ll MOD = 998244353;


ll hceil(ll a, ll b){
    return (a+b-1)/b;
}

void solve(ll testcase){
    ll n, t;
    cin>>n>>t;

    ll arr[n];
    set<ll> st;

    for(int i=0; i<n; i++){
        cin>>arr[i];
        ll temp = arr[i] % t;
        st.insert(temp);
    }

    vector<ll> v;
    for(auto u : st){
        // cout << u << " ";
        v.push_back(u);
    }
    // cout << endl;

    ll a = v[0];
    ll mx_dist = infn;
    vector<ll> idxs;
    for(int i=0; i<v.size(); i++){
        ll p1 = ((v[i] - a) % t + t) % t;
        ll p2 = ((a - v[i]) % t + t) % t;
        // cout << a << " " << p1 << " " << p2 << endl;
        ll temp = min(p1, p2);
        if(temp < mx_dist){
            continue;
        } else if(temp > mx_dist){
            mx_dist = temp;
            idxs.clear();
            idxs.push_back(i);
        } else if(temp == mx_dist){
            idxs.push_back(i);
        }
    }

    ll ans = infn;
    for(int i=0; i<idxs.size(); i++){
        a = v[idxs[i]];
        for(int j=0; j < v.size(); j++){
            ll p1 = ((v[j] - a) % t + t) % t;
            ll p2 = ((a - v[j]) % t + t) % t;
            ans = max(ans, min(p1, p2));
        }
    }

    cout << hceil(ans, 2LL) << endl;


    
    
    
    
}

int main(){
    #if __has_include("LOCAL.hh")
        #include "LOCAL.hh"
    #endif
 
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output3.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif

    int T = 1; 
    //cin>>T;
    for(int i=1; i<=T; i++){
        solve(i);
    }



 
 
    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (ld)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif
 
 
    return 0;
}

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