Submission #833092

#	Time	Username	Problem	Language	Result	Execution time	Memory
833092		skittles1412	Comparing Plants (IOI20_plants)	C++17	0 / 100	4054 ms	8928 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 << "]";
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

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 QConn {
    int n, m;
    vector<int> layers;

    QConn() {}
    QConn(int m, const vector<int>& _layers)
        : n(sz(_layers)), m(m), layers(_layers) {
        auto tmp = layers;
        layers.insert(layers.end(), begin(tmp), end(tmp));
    }

    bool query_lt(int u, int v) const {
        if (layers[u] >= layers[v]) {
            return false;
        }
        if (v < u) {
            v += n;
        }

        while (true) {
            pair<int, int> opt {int(1e9), -1};
            for (int i = u + 1; i < u + m; i++) {
                if (layers[i] > layers[u]) {
                    opt = min(opt, {layers[i], i});
                }
            }

            if (opt.second == -1) {
                break;
            }
            u = opt.second;
        }

        return v <= u;
    }
};

struct Solver {
    int n, m;
    vector<int> layers;
    QConn q_f, q_r;

    Solver() {}
    Solver(int m, const vector<int>& arr)
        : n(sz(arr)),
          m(m),
          layers(solve_layers(m, arr)),
          q_f(m, layers),
          q_r(m, reversed(layers)) {
        dbg(layers);
    }

    bool query_lt(int u, int v) const {
        return q_f.query_lt(u, v) || q_r.query_lt(n - u - 1, n - v - 1);
    }

    int query(int u, int v) const {
        if (query_lt(u, v)) {
            return -1;
        } else if (query_lt(v, u)) {
            return 1;
        }
        return 0;
    }
} 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: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25