Submission #1009369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009369		Mardonbekhazratov	Rice Hub (IOI11_ricehub)	C++17	100 / 100	338 ms	8508 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;

multiset<int>lept,rigt;
ll s1,s2;

void fix(){
    int sz=lept.size()+rigt.size();
    while(lept.size()>(sz+1)/2){
        int x=*lept.rbegin();
        rigt.insert(x);
        lept.erase(lept.find(x));
        s1-=x;
        s2+=x;
    }
    while(rigt.size()>sz/2){
        int x=*rigt.begin();
        lept.insert(x);
        rigt.erase(rigt.find(x));
        s1+=x;
        s2-=x;
    }
}

void ins(int x){
    if(lept.empty()){
        lept.insert(x);
        s1+=x;
        return;
    }
    int mid=*lept.rbegin();
    if(x>mid) rigt.insert(x),s2+=x;
    else lept.insert(x),s1+=x;
    fix();
}

void erase(int x){
    int mid=*lept.rbegin();
    if(x>mid) rigt.erase(rigt.find(x)),s2-=x;
    else lept.erase(lept.find(x)),s1-=x;
    fix();
}

int besthub(int R, int L, int X[], long long B){
    int l=1,r=R+1;
    while(r-l>1){
        int mid=(l+r)/2;
        bool ok=false;
        s1=0,s2=0;
        for(int i=0;i<R;i++){
            ins(X[i]);
            if(i>=mid) erase(X[i-mid]);
            if(i>=mid-1){
                ll x=*lept.rbegin();
                ok=ok?ok:(ll)lept.size()*x-s1+s2-(ll)rigt.size()*x<=B;
            }
        }
        multiset<int>g,j;
        swap(g,lept);
        swap(j,rigt);
        if(ok) l=mid;
        else r=mid;
    }
    return l;
}

Compilation message (stderr)

ricehub.cpp: In function 'void fix()':
ricehub.cpp:11:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |     while(lept.size()>(sz+1)/2){
      |           ~~~~~~~~~~~^~~~~~~~~
ricehub.cpp:18:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     while(rigt.size()>sz/2){
      |           ~~~~~~~~~~~^~~~~

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