Submission #1003148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003148		vjudge1	Rice Hub (IOI11_ricehub)	C++17	0 / 100	1071 ms	11092 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 calc(int n,int mid,int arr[],int B){

    multiset<pair<int,int>> lst;
    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;
        }
        ++cnt;
        B-=v.first;
    }

    return cnt;
}

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]]);
    // }
    map<int,int> comp;
    for(int i=0;i<n;i++){
        comp[arr[i]]++;
    }
    int cnt=1;
    for(auto& v:comp){
        v.second = (cnt++);
    }


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

        /*
            pointi mid e qoysaq, cavab nece olur
        */
        int mc =   calc(n,mid,arr,B);
        int lmc =  calc(n,mid-1,arr,B);
        int rmc =  calc(n,mid+1,arr,B);
        ans=max(ans,mc);
        // cout<<mid<<" "<<mc<<endl;
        if(lmc>=rmc){
            r=mid-1;
        }
        else{
            l=mid+1;
        }

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

        /*
            pointi mid e qoysaq, cavab nece olur
        */
        int mc =   calc(n,mid,arr,B);
        int lmc =  calc(n,mid-1,arr,B);
        int rmc =  calc(n,mid+1,arr,B);
        ans=max(ans,mc);
        // cout<<mid<<" "<<mc<<endl;
        if(rmc>=lmc){
            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:55:9: warning: unused variable 'anstot' [-Wunused-variable]
   55 |     int anstot=1;
      |         ^~~~~~

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