Submission #392915

#	Time	Username	Problem	Language	Result	Execution time	Memory
392915		kimbj0709	Robots (IOI13_robots)	C++14	100 / 100	1800 ms	13940 KiB

robots

#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;
  priority_queue<int> q1;
  multiset<int> set1;
  for(int i=0;i<typ1.size();i++){
    while(currpos<items.size()&&items[currpos].f<=typ1[i]){
      q1.push(items[currpos].s);
      currpos++;
    }
    for(int j=0;j<num;j++){
      if(q1.size()==0){
        break;
      }
      q1.pop();
    }
  }
  while(currpos<items.size()){
    q1.push(items[currpos].s);
    currpos++;
  }
  for(int i=0;i<typ2.size();i++){
    for(int j=0;j<num;j++){
      if(q1.size()==0){
        return 1;
      }
      if(q1.top()>typ2[i]){
        return 0;
      }
      q1.pop();
    }
  }
  if(q1.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());
  reverse(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:24: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]
   24 |   while(currpos<items.size()){
      |         ~~~~~~~^~~~~~~~~~~~~
robots.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i=0;i<typ2.size();i++){
      |               ~^~~~~~~~~~~~

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