Submission #833091

#	Time	Username	Problem	Language	Result	Execution time	Memory
833091		skittles1412	Comparing Plants (IOI20_plants)	C++17	14 / 100	4077 ms	9428 KiB

plants

#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
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25