oj.uz

Submission #833091

# Submission time Handle Problem Language Result Execution time Memory
833091 2023-08-21T23:24:02 Z skittles1412 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 9428 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

vector<int> solve_layers(int m, vector<int> arr) {
    int n = sz(arr);

    int ans_it = 0, ans_cnt = 0;
    vector<int> ans(n);

    vector<int> m_imp;

    while (ans_cnt < n) {
        while (true) {
            auto it = max_element(begin(arr), end(arr));
            if (*it == m - 1) {
                m_imp.push_back(int(it - arr.begin()));
                *it = -1e9;
            } else {
                break;
            }
        }

        sort(begin(m_imp), end(m_imp));
        dbg(m_imp, arr);

        assert(sz(m_imp));

        vector<int> n_imp;
        for (int i = 0; i < sz(m_imp); i++) {
            int prv = m_imp[(i + sz(m_imp) - 1) % sz(m_imp)], cur = m_imp[i];

            if (sz(m_imp) != 1 && (cur - prv + n) % n < m) {
                n_imp.push_back(cur);
                continue;
            }

            ans_cnt++;
            ans[cur] = ans_it;
            for (int j = 0; j < m; j++) {
                arr[(cur - j + n) % n]++;
            }
        }

        m_imp = n_imp;

        ans_it++;
    }

    return ans;
}

struct Solver {
    vector<int> layers;

    Solver() {}
    Solver(int m, const vector<int>& arr) : layers(solve_layers(m, arr)) {}

    int query(int u, int v) const {
        if (layers[u] == layers[v]) {
            return 0;
        } else if (layers[u] < layers[v]) {
            return -1;
        } else {
            return 1;
        }
    }
} solver;

void init(int m, vector<int> arr) {
    solver = Solver(m, arr);
}

int compare_plants(int u, int v) {
    return solver.query(u, v);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 166 ms 5004 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 6 ms 412 KB Output is correct
10 Correct 163 ms 5080 KB Output is correct
11 Correct 120 ms 4992 KB Output is correct
12 Correct 280 ms 5176 KB Output is correct
13 Correct 180 ms 5052 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 166 ms 5004 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 6 ms 412 KB Output is correct
10 Correct 163 ms 5080 KB Output is correct
11 Correct 120 ms 4992 KB Output is correct
12 Correct 280 ms 5176 KB Output is correct
13 Correct 180 ms 5052 KB Output is correct
14 Correct 1482 ms 5564 KB Output is correct
15 Execution timed out 4069 ms 9428 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 47 ms 4880 KB Output is correct
4 Execution timed out 4077 ms 8972 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -