Submission #1003153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003153		vjudge1	Rice Hub (IOI11_ricehub)	C++17	0 / 100	283 ms	11272 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
// #define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()

int besthub(int R, int L, int arr[], long long B){
/*
    dusun:

        hemise hansisa arr[i] e qoymaq mentiqlidi,

        binary search atib, i - j arasina gore j' - i arasini calclamaq?


            i nen j olsa, i<j'<j lerin hamisini nece costa i ye getirerik?

                arr[j']-arr[i]
                0 2 
                arr[j'+1] - arr[i] = arr[j'] -  arr[i] + (arr[j'+1]-arr[j'])
                arr[j' +2] - arr[i] = arr[j'] - arr[i] + (arr[j'+1]-arr[j']) + (arr[j'+2]-arr[j'+1])

                (arr[j'+1]-arr[j']) x (j-i)
                (arr[j'+2]-arr[j'+1]) x (j-i-1) = arr[j']

                i->j  : (arr[j'] - arr[i])*(j-i) + 
                xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


                (pref[r] - pref[l]) - ( arr[i] - arr[0] * (r-l) )
*/
    int anstot=1;
    int n = R;
    map<int,int> var;
    // vector<int> pref(R+1,0);
    // for(int i=0;i<n;i++){
    //     pref[i]=arr[i] - arr[0];
    //     if(i){
    //         pref[i]+=pref[i-1];
    //     }
    //     var[arr[i]]++;
    //     anstot= max(anstot,var[arr[i]]);
    // }
    int ans=0;
    map<int,int> comp;
    for(int i=0;i<n;i++){
        comp[arr[i]]++;
        ans=max(ans,comp[arr[i]]);
    }
    int cnt=1;
    for(auto& v:comp){
        v.second = (cnt++);
    }


    int l =1;
    int r = 1e9;
    while(l<=r){
        int mid = (l+r)/2;

        multiset<pair<int,int>> lst;
        int lq=0;
        int rq=0;
        for(int i=0;i<n;i++){
            lst.ins({abs(arr[i]-mid),i});
        }
        int cnt=0;
        for(auto v:lst){
            if(B-v.first<0){
                break;
            }
            if(abs(v.first+mid  - (mid-1))> v.first){
                lq++;
            }
            else if(abs(v.first+mid  - (mid-1))> v.first){
                lq--;
            }
            if(abs(v.first+mid - (mid+1))>v.first){
                rq++;
            }
            else if(abs(v.first+mid  - (mid+1))> v.first){
                rq--;
            }
            ++cnt;
            B-=v.first;
        }
        ans=max(ans,cnt);
        if(lq==rq){
            int a=0;
            int b= 0;
            for(int i=0;i<n;i++){
                if(abs(arr[i]-(mid-1))<abs(arr[i]-(mid+1))){
                    a++;
                }
                else if(abs(arr[i]-(mid-1))>abs(arr[i]-(mid+1))){
                    b++;
                }
            }
            if(a>=b){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        else{
            if(lq>rq){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
    } 
    // cout<<ans<<endl;
    // anstot=ans;

    return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:37:9: warning: unused variable 'anstot' [-Wunused-variable]
   37 |     int anstot=1;
      |         ^~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32