oj.uz

Submission #337834

# Submission time Handle Problem Language Result Execution time Memory
337834 2020-12-21T23:01:58 Z aanastasov Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 2097156 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 61 ms 4076 KB Output is correct
7 Execution timed out 4077 ms 55224 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 3629 ms 748 KB Output is correct
7 Execution timed out 4067 ms 7916 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 3629 ms 748 KB Output is correct
7 Execution timed out 4067 ms 7916 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 4054 ms 5100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 9 ms 492 KB Output is correct
7 Correct 133 ms 1260 KB Output is correct
8 Correct 88 ms 1260 KB Output is correct
9 Correct 107 ms 1260 KB Output is correct
10 Correct 90 ms 1280 KB Output is correct
11 Correct 127 ms 1280 KB Output is correct
12 Correct 104 ms 1260 KB Output is correct
13 Correct 129 ms 1260 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2121 ms 620 KB Output is correct
6 Runtime error 1171 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 61 ms 4076 KB Output is correct
7 Execution timed out 4077 ms 55224 KB Time limit exceeded
8 Halted 0 ms 0 KB -