Submission #550333

#	Time	Username	Problem	Language	Result	Execution time	Memory
550333		Hanksburger	Robots (IOI13_robots)	C++17	90 / 100	634 ms	22436 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> toy[1000005];
priority_queue<long long> pq;
vector<long long> vec;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
	sort(X, X+A);
	sort(Y, Y+B);
	for (long long i=0; i<T; i++)
    {
    	if (W[i]>=X[A-1] && S[i]>=Y[B-1])
    		return -1;
    	long long ind=upper_bound(X, X+A, W[i])-X, jnd=upper_bound(Y, Y+B, S[i])-Y;
    	toy[i]={ind, jnd};
	}
	sort(toy, toy+T);
    long long l=1, r=T;
    while (l<r)
    {
    	long long mid=(l+r)/2, ind=0, jnd=0, num=0;
    	for (long long i=0; i<A; i++)
    	{
    		while (ind<T && toy[ind].first<=i)
    		{
    			pq.push(toy[ind].second);
    			ind++;
			}
    		long long cnt=mid;
    		while (!pq.empty() && cnt)
    		{
    			pq.pop();
    			cnt--;
			}
		}
		while (ind<T)
		{
			pq.push(toy[ind].second);
			ind++;
		}
		vec.clear();
		while (!pq.empty())
		{
			vec.push_back(pq.top());
			pq.pop();
		}
		reverse(vec.begin(), vec.end());
		bool ok=1;
		for (long long i=0; i<vec.size(); i++)
		{
			if (jnd==B)
			{
				ok=0;
				break;
			}
			if (jnd<vec[i])
			{
				jnd=vec[i];
				num=0;
			}
			num++;
			if (num==mid)
			{
				jnd++;
				num=0;
			}
		}
		if (ok)
			r=mid;
		else
			l=mid+1;
	}
	return l;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:50:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (long long i=0; i<vec.size(); i++)
      |                       ~^~~~~~~~~~~

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