Submission #426176

#	Time	Username	Problem	Language	Result	Execution time	Memory
426176		frodakcin	Robots (IOI13_robots)	C++17	90 / 100	3047 ms	40164 KiB

robots

#include "robots.h"
#include <algorithm>
#include <set>
#include <vector>
#include <numeric>

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;

	//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];});

	if(B==0)
	{
		int ans=0;
		for(int i=0,j=0;i<A;++i)
		{
			ans = std::max(ans, (T-j+A-i-1)/(A-i));
			for(;j<T && W[ord[j]]<X[i];++j);
		}
		return ans;
	}

	int l=0, r=T;
	for(;r-l>1;)
	{
		int m=l+(r-l)/2;
		std::multiset<int> set;
		int k=0;
		for(int i=0;i<A;++i)
		{
			for(;k<T && W[ord[k]] < X[i];++k)
				set.insert(S[ord[k]]);
			for(int j=0;!set.empty() && j<m;++j)
				set.erase(std::prev(set.end()));
		}
		for(;k<T;++k)
			set.insert(S[ord[k]]);
		for(int i=0;i<B;++i)
			for(int j=0;!set.empty() && *set.begin() < Y[i] && j<m;++j)
				set.erase(set.begin());

		if(set.empty())
			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: 0 / 10