Submission #29352

#	Time	Username	Problem	Language	Result	Execution time	Memory
29352		nibnalin	Robots (IOI13_robots)	C++14	76 / 100	3000 ms	30896 KiB

robots

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include "robots.h"
using namespace std;

const int maxn = int(1e6)+5, maxs = int(5e4)+5, inf = int(1e9)+5;

int t, a, b, X[maxs], Y[maxs];
pair<int, int> A[maxn];

bool f(int x)
{
	set<pair<int, int>> undone;
	int ptr = 0;

	for(int i = 0;i < a;i++)
	{
		while(ptr < t && A[ptr].first < X[i])
		{
			undone.insert({A[ptr].second, ptr});
			ptr++;
		}

		int tmp = x;
		while(!undone.empty() && tmp--)
		{
			pair<int, int> top = *undone.rbegin();
			undone.erase(top);
		}
	}

	while(ptr < t)
	{
		undone.insert({A[ptr].second, ptr});
		ptr++;
	}

	for(int i = 0;i < b;i++)
	{
		int tmp = x;
		while(!undone.empty() && undone.begin()->first < Y[i] && tmp--)
		{
			undone.erase(undone.begin());
		}
	}
	return undone.empty();
}


int putaway(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[])
{
	a = _A, b = _B, t = _T;
	for(int i = 0;i < t;i++) A[i] = {_W[i], _S[i]};
	for(int i = 0;i < a;i++) X[i] = _X[i];
	for(int i = 0;i < b;i++) Y[i] = _Y[i];
	sort(A, A+t), sort(X, X+a), sort(Y, Y+b);

	int L = 1, R = t+1, ans = inf;
	
	while(L <= R)
	{
		int mid = (L+R)/2;
		if(f(mid)) R = mid-1, ans = min(ans, mid);
		else L = mid+1;
	}
	return ((ans > t+1)?-1:ans);
}

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