| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 983759 | totoro | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}