oj.uz

Submission #388255

# Submission time Handle Problem Language Result Execution time Memory
388255 2021-04-10T16:49:39 Z alexxela12345 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 9788 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

int n;
int k;
vector<int> r;

void genSome();

void init(int k_, std::vector<int> r_) {
	k = k_;
	r = r_;
	n = r.size();
    genSome();
}

vector<int> h;
int cur;

vector<int> tree;

void build() {
    tree = r;
}

pair<int, int> GetMin(int l, int r) {
    // l might be negative
    pair<int, int> ans = {n, -1};
    for (int i = l; i < r; i++) {
        ans = min(ans, {tree[(i + n) % n], (i + n) % n});
    }
    return ans;
}

void Set(int ind, int x) {
    tree[ind] = x;
}

void Add(int l, int r, int x) {
    for (int i = l; i < r; i++) {
        int j = (i + n) % n;
        tree[j] += x;
    }
}

void rec(int ind) {
    while (true) {
        auto pp = GetMin(ind - k + 1, ind);
        if (pp.first == 0) {
            rec(pp.second);
        } else {
            break;
        }
    }
    h[ind] = cur--;
    Set(ind, n);
    Add(ind - k + 1, ind, -1);
}

void genSome() {
    h.resize(n, -1);
    build();
    cur = n;
    while (true) {
        auto pp = GetMin(0, n);
        if (pp.first == 0) {
            rec(pp.second);
        } else {
            break;
        }
    }
}

int compare_plants(int x, int y) {
    if (h[x] > h[y]) {
        return 1;
    } else {
        return -1;
    }
}

Subtask #1
0 / 5.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 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 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 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 18 ms 364 KB Output is correct
7 Correct 451 ms 3208 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 18 ms 348 KB Output is correct
10 Correct 453 ms 3120 KB Output is correct
11 Correct 350 ms 3012 KB Output is correct
12 Correct 359 ms 3224 KB Output is correct
13 Correct 520 ms 3116 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 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 18 ms 364 KB Output is correct
7 Correct 451 ms 3208 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 18 ms 348 KB Output is correct
10 Correct 453 ms 3120 KB Output is correct
11 Correct 350 ms 3012 KB Output is correct
12 Correct 359 ms 3224 KB Output is correct
13 Correct 520 ms 3116 KB Output is correct
14 Execution timed out 4034 ms 2988 KB Time limit exceeded
15 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 0 ms 208 KB Output is correct
3 Correct 78 ms 4852 KB Output is correct
4 Execution timed out 4064 ms 9788 KB Time limit exceeded
5 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 0 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -