oj.uz

Submission #984043

# Submission time Handle Problem Language Result Execution time Memory
984043 2024-05-16T09:31:19 Z totoro Robots (IOI13_robots) C++17
39 / 100
 181 ms 65536 KB 
// SOLVED   SUBTASK 1 (14 pts)
// SOLVED   SUBTASK 2 (14 pts)
// SOLVED   SUBTASK 3 (25 pts)
// UNSOLVED SUBTASK 4 (37 pts)
// UNSOLVED SUBTASK 5 (10 pts)
// [+-+]----------------------
// TOTAL     53/100 pts

#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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Runtime error 181 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2548 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2476 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2476 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 1 ms 2476 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Runtime error 67 ms 65536 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2480 KB Output is correct
3 Correct 1 ms 2592 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Runtime error 175 ms 65536 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -