제출 #983762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983762		totoro	로봇 (IOI13_robots)	C++17	39 / 100	191 ms	65536 KiB

robots

#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;
}

컴파일 시 표준 에러 (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) {
      |                               ~~~~~~~~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10