oj.uz

Submission #434511

# Submission time Handle Problem Language Result Execution time Memory
434511 2021-06-21T11:27:16 Z yuto1115 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 14532 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int k, n;
vi r;
vi p;

void init(int _k, vi _r) {
    k = _k;
    r = _r;
    n = r.size();
    p.resize(n);
    set<int> st;
    auto check = [&](int i) {
        assert(st.count(i));
        auto it = st.lower_bound(i);
        if (it == st.begin()) {
            it = st.end();
            i += n;
        }
        it--;
        return i - *it >= k;
    };
    rep(i, n) if (!r[i]) st.insert(i);
    int nx = -1;
    for (int i : st) if (check(i)) nx = i;
    assert(nx != -1);
    rrep(t, n) {
        p[nx] = t;
        if (!t) break;
        vi can;
        auto it = st.lower_bound(nx);
        it++;
        if (it == st.end()) it = st.begin();
        if (*it != nx) can.pb(*it);
        st.erase(nx);
        rep(_, k - 1) {
            if (--nx < 0) nx += n;
            if (--r[nx] == 0) {
                st.insert(nx);
                can.pb(nx);
            }
        }
        nx = -1;
        for (int j : can) if (check(j)) nx = j;
        assert(nx != -1);
    }
}

int compare_plants(int x, int y) {
    return (p[x] > p[y] ? 1 : -1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 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 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 139 ms 3180 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 150 ms 3176 KB Output is correct
11 Correct 109 ms 3176 KB Output is correct
12 Correct 104 ms 3228 KB Output is correct
13 Correct 178 ms 3140 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 139 ms 3180 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 150 ms 3176 KB Output is correct
11 Correct 109 ms 3176 KB Output is correct
12 Correct 104 ms 3228 KB Output is correct
13 Correct 178 ms 3140 KB Output is correct
14 Correct 857 ms 3372 KB Output is correct
15 Execution timed out 4046 ms 7372 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 61 ms 3164 KB Output is correct
4 Correct 192 ms 8908 KB Output is correct
5 Runtime error 89 ms 14532 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 0 ms 204 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 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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