Submission #884775

#	Time	Username	Problem	Language	Result	Execution time	Memory
884775		dsyz	Robots (IOI13_robots)	C++17	100 / 100	1682 ms	49828 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll numW, numS, numT; //num of Weak Robots, num of Small Robots, num of Toys
vector<ll> Wlimit, Slimit; //weight limit is X, size limit is Y
deque<pair<ll,ll> > TOYS; //weight, size
bool bs(ll mid){
	deque<pair<ll,ll> > toys;
	for(ll i = 0;i < numT;i++){
		toys.push_back(TOYS[i]);
	}
	priority_queue<pair<ll,ll> > Stoys; //sort by decreasing size 
	for(ll i = 0;i < numW;i++){
		while(!toys.empty() && toys.front().first < Wlimit[i]){
			Stoys.push({toys.front().second,toys.front().first});
			toys.pop_front();
		}
		for(ll j = 0;j < mid && !Stoys.empty();j++){
			Stoys.pop();
		}
	}
	for(ll i = 0;i < toys.size();i++){
		swap(toys[i].first,toys[i].second);
	}
	while(!Stoys.empty()){
		toys.push_back(Stoys.top());
		Stoys.pop();
	}
	sort(toys.begin(),toys.end());
	for(ll i = 0;i < numS;i++){
		for(ll j = 0;j < mid && !toys.empty();j++){
			if(toys.front().first >= Slimit[i]) break;
			toys.pop_front();
		}
	}
	return toys.empty(); 
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	numW = A;
	numS = B;
	numT = T;
	for(ll i = 0;i < numW;i++){
		Wlimit.push_back(X[i]);
	}
	for(ll i = 0;i < numS;i++){
		Slimit.push_back(Y[i]);
	}
	for(ll i = 0;i < numT;i++){
		TOYS.push_back({W[i],S[i]});
	}
	sort(Wlimit.begin(),Wlimit.end());
	sort(Slimit.begin(),Slimit.end());
	sort(TOYS.begin(),TOYS.end());
	ll high = T + 5;
	ll low = 0;
	bool ok = 0;
	while(high - low > 1){
		ll mid = (high + low) / 2;
		if(bs(mid)){
			high = mid;
			ok = 1;
		}else{
			low = mid;
		}
	}
	if(!ok){
		return -1;
	}else{
		return high;
	}
}

Compilation message (stderr)

robots.cpp: In function 'bool bs(ll)':
robots.cpp:24:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(ll i = 0;i < toys.size();i++){
      |               ~~^~~~~~~~~~~~~

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