oj.uz

Submission #145257

# Submission time Handle Problem Language Result Execution time Memory
145257 2019-08-19T11:50:27 Z faremy Robots (IOI13_robots) C++14
100 / 100
 2802 ms 40392 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 399 ms 28340 KB Output is correct
5 Correct 436 ms 37728 KB Output is correct
6 Correct 63 ms 7148 KB Output is correct
7 Correct 391 ms 35656 KB Output is correct
8 Correct 486 ms 34960 KB Output is correct
9 Correct 431 ms 37548 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1556 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1532 KB Output is correct
12 Correct 3 ms 1528 KB Output is correct
13 Correct 3 ms 1532 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Correct 3 ms 1528 KB Output is correct
13 Correct 3 ms 1528 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct
15 Correct 3 ms 1528 KB Output is correct
16 Correct 14 ms 2104 KB Output is correct
17 Correct 14 ms 2044 KB Output is correct
18 Correct 14 ms 1976 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 405 ms 28336 KB Output is correct
11 Correct 460 ms 37584 KB Output is correct
12 Correct 62 ms 7144 KB Output is correct
13 Correct 394 ms 35400 KB Output is correct
14 Correct 467 ms 34892 KB Output is correct
15 Correct 3 ms 1528 KB Output is correct
16 Correct 3 ms 1528 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 3 ms 1528 KB Output is correct
19 Correct 3 ms 1528 KB Output is correct
20 Correct 3 ms 1528 KB Output is correct
21 Correct 14 ms 2300 KB Output is correct
22 Correct 2802 ms 38624 KB Output is correct
23 Correct 457 ms 37636 KB Output is correct
24 Correct 513 ms 38472 KB Output is correct
25 Correct 642 ms 36468 KB Output is correct
26 Correct 1100 ms 40392 KB Output is correct
27 Correct 847 ms 38852 KB Output is correct
28 Correct 842 ms 38756 KB Output is correct
29 Correct 748 ms 38728 KB Output is correct