Submission #983762

#TimeUsernameProblemLanguageResultExecution timeMemory
983762totoroRobots (IOI13_robots)C++17
39 / 100
191 ms65536 KiB
#include "robots.h" #include <algorithm> #include <unordered_set> #include <vector> const size_t MAX_SIZE_WEIGHT = 2000000001; 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], MAX_SIZE_WEIGHT)); } for (size_t smallRobot = 0; smallRobot < B; ++smallRobot) { robots.push_back(new Robot(MAX_SIZE_WEIGHT, 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; }

Compilation message (stderr)

robots.cpp: In function 'bool canSolve(const std::vector<Robot*>&, int, int)':
robots.cpp:41:28: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             if (isCarrying >= minutesTarget) {
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~~~~
robots.cpp:50:25: warning: comparison of integer expressions of different signedness: 'std::unordered_set<Toy*>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     return taken.size() == T;
      |            ~~~~~~~~~~~~~^~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:72:42: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (size_t weakRobot = 0; weakRobot < A; ++weakRobot) {
      |                                ~~~~~~~~~~^~~
robots.cpp:75:44: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     for (size_t smallRobot = 0; smallRobot < B; ++smallRobot) {
      |                                 ~~~~~~~~~~~^~~
robots.cpp:78:40: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |     for (size_t toyIndex = 0; toyIndex < T; ++toyIndex) {
      |                               ~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...