Submission #983758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
983758	2024-05-16T04:47:34 Z	totoro	Robots (IOI13_robots)	C++17	Compilation error	0 ms	0 KB

robots

#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_T_MAX));
    }
    for (size_t smallRobot = 0; smallRobot < B; ++smallRobot) {
        robots.push_back(new Robot(SIZE_T_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;
}

Compilation message

robots.cpp: In function 'bool canSolve(const std::vector<Robot*>&, int, int)':
robots.cpp:40:28: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |             if (isCarrying >= minutesTarget) {
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~~~~
robots.cpp:49:25: warning: comparison of integer expressions of different signedness: 'std::unordered_set<Toy*>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |     return taken.size() == T;
      |            ~~~~~~~~~~~~~^~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:71:42: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     for (size_t weakRobot = 0; weakRobot < A; ++weakRobot) {
      |                                ~~~~~~~~~~^~~
robots.cpp:72:50: error: 'SIZE_T_MAX' was not declared in this scope; did you mean 'SSIZE_MAX'?
   72 |         robots.push_back(new Robot(X[weakRobot], SIZE_T_MAX));
      |                                                  ^~~~~~~~~~
      |                                                  SSIZE_MAX
robots.cpp:74:44: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     for (size_t smallRobot = 0; smallRobot < B; ++smallRobot) {
      |                                 ~~~~~~~~~~~^~~
robots.cpp:75:36: error: 'SIZE_T_MAX' was not declared in this scope; did you mean 'SSIZE_MAX'?
   75 |         robots.push_back(new Robot(SIZE_T_MAX, Y[smallRobot]));
      |                                    ^~~~~~~~~~
      |                                    SSIZE_MAX
robots.cpp:77:40: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     for (size_t toyIndex = 0; toyIndex < T; ++toyIndex) {
      |                               ~~~~~~~~~^~~