oj.uz

Submission #833092

# Submission time Handle Problem Language Result Execution time Memory
833092 2023-08-21T23:54:47 Z skittles1412 Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 8928 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, 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 43 ms 4016 KB Output is correct
7 Correct 425 ms 5952 KB Output is correct
8 Execution timed out 4051 ms 8928 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 0 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 137 ms 368 KB Output is correct
7 Execution timed out 4046 ms 2792 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 0 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 137 ms 368 KB Output is correct
7 Execution timed out 4046 ms 2792 KB Time limit exceeded
8 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 1244 ms 3108 KB Output is correct
4 Execution timed out 4054 ms 6016 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 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 Incorrect 17 ms 340 KB Output isn't correct
6 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 43 ms 4016 KB Output is correct
7 Correct 425 ms 5952 KB Output is correct
8 Execution timed out 4051 ms 8928 KB Time limit exceeded
9 Halted 0 ms 0 KB -