1631D - Range and Partition - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    for(auto &i:v) cin>>i;
    int req = (n+k+1)/2;
    auto vv = v;
    sort(vv.begin(),vv.end());
    vector<int> ans = {n+1,-1,-1};
    for(int i=0;i<n-req+1;i++){
        int d = vv[i+req-1] - vv[i];
        ans = min(ans,{d,vv[i],vv[i+req-1]});
    }
    int x = ans[1],y = ans[2];
    int sum = 0,cnt = 0,prev = 1;
    cout<<x<<" "<<y<<endl;
    for(int i=0;i<n;i++){
        if(v[i] >= x && v[i]<= y) sum++;
        else sum--;
        if(sum > 0 && cnt < k-1){
            cout<<prev<<" "<<i+1<<endl;
            prev = i+2;
            sum = 0;
            cnt++;
        }
    }
    cout<<prev<<" "<<n<<endl;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    // for(int i=12;i<=12;i++){
    //     int n = (1<<i);
    //     for(int k = 0;k<n-1;k++){
    //         auto res = solve(n,k);
    //         int x = 0;
    //         for(auto &p:res) x = x + (p.first & p.second);
    //         if(x != k) cout<<n<<" "<<k<<" "<<x<<endl;
    //     }
    // }
}