Submission #337834

#	Time	Username	Problem	Language	Result	Execution time	Memory
337834		aanastasov	Comparing Plants (IOI20_plants)	C++17	11 / 100	4077 ms	2097156 KiB

plants

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#include "plants.h"

template<typename T> void debug(std::vector<T> v) {
    std::cout << "{";
    for (int i = 0; i < v.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << v[i];
    }
    std::cout << "}\n";
}

class PlantsSolver {
public:
    PlantsSolver() { }
    PlantsSolver(int k, std::vector<int> r) {
        const int numPlants = r.size();
        const int infty = 1e9;
        maybeShorter = std::vector<std::vector<bool>>(numPlants,
                std::vector<bool>(numPlants, true));
        for (int curPlant = 0; curPlant < numPlants; ++curPlant) {
            auto ranks = std::vector<int>(r.begin(), r.end());
            for (int h = numPlants; h >= 1; --h) {
                auto zeroes = std::vector<int>();
                for (int i = 0; i < numPlants; ++i) if (ranks[i] == 0) {
                    zeroes.push_back(i);
                }
                assert(!zeroes.empty());
                auto candidates = std::vector<int>();
                for (int i = 0; i < zeroes.size(); ++i) {
                    int offset = zeroes[i] - zeroes[(i - 1 + zeroes.size()) % zeroes.size()];
                    if (i == 0) offset += numPlants;
                    if (offset >= k || zeroes.size() == 1) {
                        candidates.push_back(zeroes[i]);
                    }
                }
                assert(!candidates.empty());
                if (candidates.size() == 1 && candidates[0] == curPlant) {
                    break;
                } else {
                    int x = candidates[0] != curPlant ? candidates[0] : candidates[1];
                    maybeShorter[curPlant][x] = false;
                    assert(x != curPlant);
                    ranks[x] = infty;
                    for (int offset = 1; offset < k; ++offset) {
                        int preceding = (x - offset + numPlants) % numPlants;
                        ranks[preceding]--;
                        assert(ranks[preceding] >= 0);
                    }
                }
            }
        }
    }

    int comparePlants(int x, int y) {
        const bool xToY = maybeShorter[x][y];
        const bool yToX = maybeShorter[y][x];
        if (xToY != yToX) {
            if (yToX) return -1;
            else return 1;
        } else {
            return 0;
        }
    }

    std::vector<std::vector<bool>> maybeShorter;
};

PlantsSolver solver;

void init(int k, std::vector<int> r) {
    solver = PlantsSolver(k, r);
}

int compare_plants(int x, int y) {
    return solver.comparePlants(x, y);
}

Compilation message (stderr)

plants.cpp: In constructor 'PlantsSolver::PlantsSolver(int, std::vector<int>)':
plants.cpp:34:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 for (int i = 0; i < zeroes.size(); ++i) {
      |                                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25