Submission #96358

#	Time	Username	Problem	Language	Result	Execution time	Memory
96358		figter001	Robots (IOI13_robots)	C++14	0 / 100	3 ms	504 KiB

robots

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

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

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

bool can(int md){
	for(int x=0;x<t;x++)used[x] = 0;
	int id1 = 0,id2 = 0,i = 0,j = 0;
	for(int x=0;x<t;x++){
		while(i < t && used[tw[i].second])i++;
		while(j < t && used[ts[j].second])j++;
		if(id1 == w.size() && id2 == s.size())break;
		if(id1 == w.size() || s[id2] < w[id1]){
			int cur = s[id2];
			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++;
			}
			id2++;
		}else{
			int cur = w[id1];
			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++;
			}
			id1++;
		}
	}
	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]);
	for(int i=0;i<B;i++)s.push_back(Y[i]);
	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(s.begin(),s.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:20:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(id1 == w.size() && id2 == s.size())break;
      ~~~~^~~~~~~~~~~
robots.cpp:20:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(id1 == w.size() && id2 == s.size())break;
                         ~~~~^~~~~~~~~~~
robots.cpp:21:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(id1 == w.size() || s[id2] < w[id1]){
      ~~~~^~~~~~~~~~~

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