제출 #145257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145257		faremy	로봇 (IOI13_robots)	C++14	100 / 100	2802 ms	40392 KiB

robots

#include "robots.h"

#include <algorithm>
#include <vector>
#include <queue>


struct Item
{
	Item(int l, int o, int c) : limit(l), othLim(o), carrying(c) {}
	int limit, othLim, carrying;

	bool operator <(const Item &other) const
	{
		return (other.carrying < carrying);
	}
};

const int MAXN = 1e6;
const int MAXA = 5e4;

int weight[MAXN], size[MAXN];
int weightLimit[MAXA];
int sizeLimit[MAXA];

std::vector<Item> toSort;
std::priority_queue<Item> sorting;

std::vector<Item> given[MAXA];
std::vector<Item> unsorted;


bool cmplimit(const Item &a, const Item &b)
{
	if (a.limit != b.limit)
		return (a.limit > b.limit);
	return (a.carrying < b.carrying);
}

bool cansolve(int time, int toys, int weak, int small)
{
	toSort.clear();
	while (!sorting.empty())
		sorting.pop();

	for (const Item &toy : unsorted)
		toSort.emplace_back(toy);
	for (int iRob = 0; iRob < weak; iRob++)
		for (int iToy = given[iRob].size() - 1; iToy >= time; iToy--)
			toSort.emplace_back(given[iRob][iToy]);

	for (int iRob = 0; iRob < small; iRob++)
		toSort.emplace_back(sizeLimit[iRob], iRob, 0);
	std::sort(toSort.begin(), toSort.end(), cmplimit);

	if (!toSort.empty() && toSort.front().carrying == -1)
		return false;
	int maxTime = 0;

	for (const Item &item : toSort)
	{
		if (item.carrying == 0)
			sorting.emplace(item);
		else
		{
			Item robot = sorting.top();
			sorting.pop();
			
			maxTime = std::max(maxTime, robot.carrying + 1);
			sorting.emplace(robot.limit, robot.othLim, robot.carrying + 1);
		}
	}

	return (maxTime <= time);
}

int searchans(int left, int right, int toys, int weak, int small)
{
	if (left == right)
		return toys + 1;
	int time = (left + right) / 2;

	if (cansolve(time, toys, weak, small))
		return std::min(time, searchans(left, time, toys, weak, small));
	return searchans(time + 1, right, toys, weak, small);
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
	int weak = A, small = B, toys = T;
	for (int iRob = 0; iRob < weak; iRob++)
		weightLimit[iRob] = X[iRob];
	for (int iRob = 0; iRob < B; iRob++)
		sizeLimit[iRob] = Y[iRob];

	for (int iToy = 0; iToy < toys; iToy++)
	{
		weight[iToy] = W[iToy];
		size[iToy] = S[iToy];
	}

	for (int iRob = 0; iRob < weak; iRob++)
		toSort.emplace_back(weightLimit[iRob], iRob, 0);
	for (int iToy = 0; iToy < toys; iToy++)
		toSort.emplace_back(weight[iToy], size[iToy], -1);

	std::sort(toSort.begin(), toSort.end(), cmplimit);
	for (const Item &item : toSort)
	{
		if (item.carrying == 0)
			sorting.emplace(item);
		else if (sorting.empty())
			unsorted.emplace_back(item.othLim, item.limit, -1);
		else
		{
			Item robot = sorting.top();
			sorting.pop();

			given[robot.othLim].emplace_back(item.othLim, item.limit, -1);
			sorting.emplace(robot.limit, robot.othLim, robot.carrying + 1);
		}
	}

	for (int iRob = 0; iRob < weak; iRob++)
		std::sort(given[iRob].begin(), given[iRob].end(), cmplimit);
	int minTime = searchans(1, toys + 1, toys, weak, small);

	if (minTime == toys + 1)
		return -1;
	else
		return minTime;
	return 0;
}

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