| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 983759 | totoro | Robots (IOI13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "robots.h"
#include <algorithm>
#include <climits>
#include <unordered_set>
#include <vector>
struct Robot;
struct Toy;
struct Robot {
std::vector<Toy*> cargo;
size_t weightLimit;
size_t sizeLimit;
Robot(size_t weightLimit, size_t sizeLimit) : weightLimit(weightLimit), sizeLimit(sizeLimit) {}
};
struct Toy {
std::vector<Robot*> carriers;
size_t weight;
size_t size;
Toy(size_t weight, size_t size) : weight(weight), size(size) {}
};
struct CompareRobots {
bool operator()(Robot* a, Robot* b) {
return a->cargo.size() <= b->cargo.size();
}
};
struct CompareToys {
bool operator()(Toy* a, Toy* b) {
return a->carriers.size() <= b->carriers.size();
}
};
bool canSolve(const std::vector<Robot*>& robots, int T, int minutesTarget) {
std::unordered_set<Toy*> taken;
for (auto robot : robots) {
size_t isCarrying = 0;
for (auto toy : robot->cargo) {
if (isCarrying >= minutesTarget) {
break;
}
if (!taken.count(toy)) {
taken.insert(toy);
++isCarrying;
}
}
}
return taken.size() == T;
}
int binarySearch(const std::vector<Robot*>& robots, int T, int lowerBound, int upperBound) {
if (upperBound == lowerBound) {
return upperBound;
}
int target = (lowerBound + upperBound) / 2;
if (canSolve(robots, T, target)) {
return binarySearch(robots, T, lowerBound, target);
} else {
return binarySearch(robots, T, target + 1, upperBound);
}
}
bool canCarry(Robot* robot, Toy* toy) {
return toy->weight < robot->weightLimit && toy->size < robot->sizeLimit;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
std::vector<Robot*> robots;
for (size_t weakRobot = 0; weakRobot < A; ++weakRobot) {
robots.push_back(new Robot(X[weakRobot], SIZE_MAX));
}
for (size_t smallRobot = 0; smallRobot < B; ++smallRobot) {
robots.push_back(new Robot(SIZE_MAX, Y[smallRobot]));
}
for (size_t toyIndex = 0; toyIndex < T; ++toyIndex) {
Toy* toy = new Toy(W[toyIndex], S[toyIndex]);
bool carryable = false;
for (auto robot : robots) {
if (canCarry(robot, toy)) {
robot->cargo.push_back(toy);
toy->carriers.push_back(robot);
carryable = true;
}
}
if (!carryable) {
return -1;
}
}
std::sort(robots.begin(), robots.end(), CompareRobots());
for (auto robot : robots) {
std::sort(robot->cargo.begin(), robot->cargo.end(), CompareToys());
}
int result = binarySearch(robots, T, (T - 1) / (A + B) + 1, T);
return result;
}