Submission #897533

#	Time	Username	Problem	Language	Result	Execution time	Memory
897533		ThylOne	Rice Hub (IOI11_ricehub)	C++14	17 / 100	1067 ms	2008 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>

using namespace std;
using pll = pair<long long,long long>;
vector<pll> pos;
long long budget;
int limit;
bool existWithT(int T){
  long long sum = 0;
  int taille = 0;
  int right=0;
  for(int left=0;left<pos.size();left++){
    while(taille<T && right<pos.size()){
      taille+=pos[right].second;
      sum+=pos[right].first*pos[right].second;
      right++;
    }
    if(taille<T)break;
    double bestInf = double(sum)/double(taille);
    double bestSup = ceil(double(sum)/double(taille));
    auto scoring = [&](int x){
      long long re = 0;
      for(int i=left;i<right;i++)
        re+=pos[i].second * abs(x-pos[i].first);
      return re;
    };
    if(scoring(bestInf)<=budget || scoring(bestSup)<=budget)return true;
    taille-=pos[left].second;
    sum-=pos[left].first*pos[left].second;
  }
  return false;
}
int besthub(int R, int L, int X[], long long B)
{

  budget = B;
  
  limit = L;
  map<int,int> occ;
  for(int i = 0;i<R;i++){
    occ[X[i]]++;
  }
  for(int i = 0;i<R;i++){
    if(occ[X[i]])
      pos.push_back({X[i],occ[X[i]]});
    occ[X[i]]=0;
  }
  sort(pos.begin(),pos.end());
  for(int i=R;i>=1;i--){
    if(existWithT(i)){
      return i;
    }
  }
}

Compilation message (stderr)

ricehub.cpp: In function 'bool existWithT(int)':
ricehub.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for(int left=0;left<pos.size();left++){
      |                  ~~~~^~~~~~~~~~~
ricehub.cpp:14:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     while(taille<T && right<pos.size()){
      |                       ~~~~~^~~~~~~~~~~
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:40:16: warning: control reaches end of non-void function [-Wreturn-type]
   40 |   map<int,int> occ;
      |                ^~~

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