Submission #392907

#	Time	Username	Problem	Language	Result	Execution time	Memory
392907		kimbj0709	Robots (IOI13_robots)	C++14	76 / 100	3088 ms	25156 KiB

robots

#pragma GCC optimize("O3")
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
vector<pair<int,int> > items;
vector<int> typ1,typ2;
bool can(int num){
  int currpos = 0;
  multiset<int> set1;
  for(int i=0;i<typ1.size();i++){
    while(currpos<items.size()&&items[currpos].f<=typ1[i]){
      set1.insert(items[currpos].s);
      currpos++;
    }
    for(int j=0;j<num;j++){
      if(set1.size()==0){
        break;
      }
      auto k = set1.end();
      k--;
      set1.erase(k);
    }
  }
  while(currpos<items.size()){
    set1.insert(items[currpos].s);
    currpos++;
  }
  for(int i=0;i<typ2.size();i++){
    for(int j=0;j<num;j++){
      if(set1.size()==0){
        return 1;
      }
      auto k = set1.upper_bound(typ2[i]);
      if(k==set1.begin()){
        break;
      }
      k--;
      set1.erase(k);
    }
  }
  if(set1.size()==0){
    return 1;
  }
  return 0;


}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  for(int i=0;i<A;i++){
    X[i]--;
    typ1.push_back(X[i]);
  }
  for(int i=0;i<B;i++){
    Y[i]--;
    typ2.push_back(Y[i]);
  }
  for(int i=0;i<T;i++){
    items.push_back({W[i],S[i]});
  }
  sort(items.begin(),items.end());
  sort(typ1.begin(),typ1.end());
  sort(typ2.begin(),typ2.end());
  int lo = 0,hi = T+3;
  while(lo+1!=hi){
    int mid = (lo+hi)/2;
    if(can(mid)){
      hi = mid;
    }
    else{
      lo = mid;
    }
  }
  if(lo>T){
      return -1;
  }
  return lo+1;
}

Compilation message (stderr)

robots.cpp: In function 'bool can(int)':
robots.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   for(int i=0;i<typ1.size();i++){
      |               ~^~~~~~~~~~~~
robots.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     while(currpos<items.size()&&items[currpos].f<=typ1[i]){
      |           ~~~~~~~^~~~~~~~~~~~~
robots.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   while(currpos<items.size()){
      |         ~~~~~~~^~~~~~~~~~~~~
robots.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=0;i<typ2.size();i++){
      |               ~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10