oj.uz

Submission #833093

# Submission time Handle Problem Language Result Execution time Memory
833093 2023-08-22T00:11:19 Z skittles1412 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 9960 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 << "]";
}

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, logn, m;
    vector<int> layers;
    vector<vector<int>> lift;

    QConn() {}
    QConn(int m, const vector<int>& _layers)
        : n(sz(_layers)), logn(__lg(n) + 3), m(m), layers(_layers), lift(logn + 1, vector<int>(2 * n)) {
        auto tmp = layers;
        layers.insert(layers.end(), begin(tmp), end(tmp));

        map<int, int> q;
        for (int i = 2 * n - 1; i >= 0; i--) {
            if (i + m < 2 * n) {
                q.erase(layers[i + m]);
            }
            assert(!q.count(layers[i]));
            q[layers[i]] = i;

            auto it = q.upper_bound(layers[i]);
            if (it == q.end()) {
                lift[0][i] = -1;
            } else {
                lift[0][i] = it->second;
            }
        }

        for (int i = 1; i <= logn; i++) {
            for (int j = 0; j < 2 * n; j++) {
                if (lift[i - 1][j] == -1) {
                    lift[i][j] = -1;
                } else {
                    lift[i][j] = lift[i - 1][lift[i - 1][j]];
                }
            }
        }
    }

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

        for (int i = logn; i >= 0; i--) {
            int nu = lift[i][u];
            if (nu != -1 && layers[nu] <= layers[v]) {
                u = nu;
            }
        }

        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.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 0 ms 212 KB Output is correct
4 Correct 1 ms 260 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 41 ms 3020 KB Output is correct
7 Correct 364 ms 9568 KB Output is correct
8 Execution timed out 4030 ms 6028 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 260 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 632 KB Output is correct
7 Correct 172 ms 4684 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 596 KB Output is correct
10 Correct 172 ms 4684 KB Output is correct
11 Correct 156 ms 4572 KB Output is correct
12 Correct 309 ms 4680 KB Output is correct
13 Correct 198 ms 4768 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 260 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 632 KB Output is correct
7 Correct 172 ms 4684 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 596 KB Output is correct
10 Correct 172 ms 4684 KB Output is correct
11 Correct 156 ms 4572 KB Output is correct
12 Correct 309 ms 4680 KB Output is correct
13 Correct 198 ms 4768 KB Output is correct
14 Correct 1466 ms 9960 KB Output is correct
15 Execution timed out 4024 ms 5708 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 67 ms 3560 KB Output is correct
4 Execution timed out 4038 ms 6176 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 12 ms 1236 KB Output is correct
8 Correct 10 ms 1236 KB Output is correct
9 Correct 12 ms 1236 KB Output is correct
10 Correct 11 ms 1236 KB Output is correct
11 Correct 12 ms 1236 KB Output is correct
12 Correct 12 ms 1332 KB Output is correct
13 Correct 11 ms 1236 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Execution timed out 4022 ms 8008 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 0 ms 212 KB Output is correct
4 Correct 1 ms 260 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 41 ms 3020 KB Output is correct
7 Correct 364 ms 9568 KB Output is correct
8 Execution timed out 4030 ms 6028 KB Time limit exceeded
9 Halted 0 ms 0 KB -