Submission #29354

#	Time	Username	Problem	Language	Result	Execution time	Memory
29354		nibnalin	Robots (IOI13_robots)	C++14	28 / 100	359 ms	23576 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], undone[maxn];
pair<int, int> A[maxn];
vector<int> guys[maxs];

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

	for(int i = 0;i < a;i++)
	{
		if(int(guys[i].size()) < x)
		{
			int tmp = x-int(guys[i].size());
			undone = max(0, undone-tmp);
		}
		else
		{
			for(int j = 0;j < int(guys[i].size())-x;j++)
			{
				if(ptr.first == b)
				{
					undone++;
					continue;
				}
				
				while(ptr.first < b && (guys[i][j] >= Y[ptr.first] || !ptr.second)) ptr.first++, ptr.second = x;
				if(ptr.first == b)
				{
					undone++;
					continue;
				}
				
				ptr.second--;
			}
		}
	}

	for(int j = 0;j < int(guys[a].size());j++)
	{
		if(ptr.first == b)
		{
			undone++;
			continue;
		}
				
		while(ptr.first < b && (guys[a][j] >= Y[ptr.first] || !ptr.second)) ptr.first++, ptr.second = x;
		if(ptr.first == b)
		{
			undone++;
			continue;
		}
				
		ptr.second--;
	}

	//cout << x << " " << undone << "\n";
	return !undone;
}


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 ptr = 0;
	for(int i = 0;i < a;i++)
	{
		while(ptr < t && A[ptr].first < X[i])
		{
			guys[i].push_back(A[ptr].second);
			ptr++;
		}
		sort(guys[i].begin(), guys[i].end());
	}
	while(ptr < t)
	{
		guys[a].push_back(A[ptr].second);
		ptr++;
	}
	sort(guys[a].begin(), guys[a].end());

	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: 14 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10