Submission #96364

#	Time	Username	Problem	Language	Result	Execution time	Memory
96364		figter001	Robots (IOI13_robots)	C++14	100 / 100	468 ms	27360 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
  
using namespace std;

typedef long long ll;
const int maxt = 1e6+50;

vector<pair<int,int>> tw,ts,w;
int t;
bool used[maxt];

bool can(int md){
	for(int x=0;x<t;x++)used[x] = 0;
	int i = 0,j = 0;
	for(int x=0;x<w.size();x++){
		if(w[x].second == 1){
			int cur = w[x].first;
			int use = 0;
			while(use < md && j < t && cur > ts[j].first){
				if(used[ts[j].second]){
					j++;
					continue;
				}
				used[ts[j].second] = 1;
				j++;
				use++;
			}
		}else{
			int cur = w[x].first;
			int use = 0;
			while(use < md && i < t && cur > tw[i].first){
				if(used[tw[i].second]){
					i++;
					continue;
				}
				used[tw[i].second] = 1;
				i++;
				use++;
			}
		}
	}
	for(int x=0;x<t;x++)if(!used[x])return 0;
	return 1;
}	

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
	t = T;
	for(int i=0;i<A;i++)w.push_back({X[i],0});
	for(int i=0;i<B;i++)w.push_back({Y[i],1});
	for(int i=0;i<T;i++)tw.push_back({W[i],i});
	for(int i=0;i<T;i++)ts.push_back({S[i],i});
	sort(w.begin(),w.end());
	sort(tw.begin(),tw.end());
	sort(ts.begin(),ts.end());
	int md,lo=0,hi=T,ans=-1;
	while(lo <= hi){
		md = (lo+hi)/2;
		if(can(md)){
			ans = md;
			hi = md-1;
		}else lo = md+1;
	}
	return ans;
}

Compilation message (stderr)

robots.cpp: In function 'bool can(int)':
robots.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0;x<w.size();x++){
              ~^~~~~~~~~

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