Submission #426381

#	Time	Username	Problem	Language	Result	Execution time	Memory
426381		frodakcin	Robots (IOI13_robots)	C++17	100 / 100	1708 ms	19380 KiB

robots

#include "robots.h"
#include <cassert>
#include <algorithm>
#include <map>
#include <vector>
#include <numeric>
#include <functional>

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
	std::sort(X, X+A);
	std::sort(Y, Y+B);
	for(int i=0;i<T;++i)
		if((A==0||W[i]>=X[A-1]) && (B==0||S[i]>=Y[B-1]))
			return -1;

	for(int i=0;i<T;++i)
	{
		W[i] = A?std::lower_bound(X, X+A, W[i]+1)-X:0;
		assert(0 <= W[i] && W[i] <= A);
		S[i] = B?std::lower_bound(Y, Y+B, S[i]+1)-Y:0;
		assert(0 <= S[i] && S[i] <= B);
	}

	//must be possible;
	std::vector<int> ord(T);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [&](int u, int v){return W[u]<W[v];});

	int l=0, r=T;
	for(;r-l>1;)
	{
		int m=l+(r-l)/2;
		int j=0;
		std::map<int, int> map;
		for(int i=0;i<=A;++i)
		{
			for(;j < T && W[ord[j]] == i;++j)
				++map[S[ord[j]]];
			if(i<A)
				for(int rem=m;rem>0 && !map.empty();)
				{
					auto it=std::prev(map.end());
					if(rem >= it->second)
						rem -= it->second, map.erase(it);
					else
						it->second -= rem, rem=0;
				}
		}
		assert(j == T);

		int c=0;
		for(int i=0;i<=B;++i)
		{
			if(!map.empty() && map.begin()->first == i)
				c += map.begin()->second, map.erase(map.begin());
			if(i<B)
				c=std::max(c-m, 0);
		}
		if(c==0) // good
			r=m;
		else
			l=m;
	}
	return r;
}

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