oj.uz

Submission #301558

# Submission time Handle Problem Language Result Execution time Memory
301558 2020-09-18T04:20:40 Z kevinsogo Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 13808 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int mod(int a, int n) {
    if ((a %= n) < 0) a += n;
    return a;
}

int n, k;
int dist(int i, int j) {
    return mod(j - i - 1, n) + 1;
}

vector<int> rts, lfs, vals;
vector<ll> rtdists, lfdists;
void init(int k_, vector<int> r) {
    k = k_;
    n = r.size();
    vals = vector<int>(n, -1);

    vector<int> likod(n), harap(n);
    unordered_set<int> oks;

    vector<int> cands;
    for (int i = 0; i < n; i++) if (r[i] == 0) cands.push_back(i);
    for (int x2 = 0, x1 = cands.size() - 1; x2 < cands.size(); x1 = x2++) {
        int j1 = cands[x1], j2 = cands[x2];
        harap[j1] = j2;
        likod[j2] = j1;
        if (dist(j1, j2) >= k) oks.insert(j2);
    }
    
    for (int v = n; v--;) {
        int j = *oks.begin();
        int j1 = likod[j], j2 = harap[j];
        oks.erase(j);
        vals[j] = v;
        r[j] += n + 1;
        vector<int> bagos;
        for (int l = j - k + 1; l < j; l++) {
            int ln = mod(l, n);
            if (!--r[ln]) bagos.push_back(ln);
        }

        if (v > 0) {
            if (j == j1 && j == j2) {
                j1 = bagos.back();
                j2 = bagos.front();
            }

            bagos.insert(bagos.begin(), j1);
            bagos.push_back(j2);
            for (int x1 = 0, x2 = 1; x2 < bagos.size(); x1++, x2++) {
                int j1 = bagos[x1], j2 = bagos[x2];
                harap[j1] = j2;
                likod[j2] = j1;
                if (dist(j1, j2) >= k) {
                    oks.insert(j2);
                } else if (oks.count(j2)) {
                    oks.erase(j2);
                }
            }
        }
    }

    rts = vector<int>(n, -1);
    lfs = vector<int>(n, -1);
    vector<int> wals(n, -2), inds(n);
    iota(inds.begin(), inds.end(), 0);
    sort(inds.begin(), inds.end(), [&](int i, int j) { return vals[i] < vals[j]; });
    for (int x : inds) {
        rts[x] = lfs[x] = x;
        for (int i = x; i < x + k; i++) {
            if (wals[rts[x]] < wals[mod(i, n)]) rts[x] = mod(i, n);
        }
        for (int i = x - k + 1; i <= x; i++) {
            if (wals[lfs[x]] < wals[mod(i, n)]) lfs[x] = mod(i, n);
        }
        wals[x] = vals[x];
    }

    lfdists.resize(n);
    rtdists.resize(n);
    for (int i = 0; i < n; i++) {
        lfdists[i] = dist(lfs[i], i);
        rtdists[i] = dist(i, rts[i]);
    }
}

pair<int,ll> walk_up(const vector<int>& par, const vector<ll>& dists, int i, ll d) {
    while (d >= dists[i]) {
        d -= dists[i];
        i = par[i];
    }
    return {i, d};
}

bool is_fixed_right(int x, int y) {
    auto [X, rem] = walk_up(rts, rtdists, x, dist(x, y));
    return rem < k && vals[X] >= vals[y];
}

bool is_fixed_left(int x, int y) {
    auto [X, rem] = walk_up(lfs, lfdists, x, dist(y, x));
    return rem < k && vals[X] >= vals[y];
}

int compare_plants(int x, int y) {
    int mul = 1;
    if (vals[x] < vals[y]) {
        swap(x, y);
        mul = -1;
    }

    return (is_fixed_right(x, y) || is_fixed_left(x, y)) * mul;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:28:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int x2 = 0, x1 = cands.size() - 1; x2 < cands.size(); x1 = x2++) {
      |                                             ~~~^~~~~~~~~~~~~~
plants.cpp:55:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for (int x1 = 0, x2 = 1; x2 < bagos.size(); x1++, x2++) {
      |                                      ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 72 ms 3192 KB Output is correct
7 Correct 143 ms 4188 KB Output is correct
8 Correct 209 ms 13808 KB Output is correct
9 Correct 266 ms 13424 KB Output is correct
10 Correct 656 ms 13552 KB Output is correct
11 Execution timed out 4035 ms 13424 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 451 ms 3448 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 18 ms 384 KB Output is correct
10 Correct 470 ms 3416 KB Output is correct
11 Correct 1136 ms 3388 KB Output is correct
12 Correct 722 ms 3540 KB Output is correct
13 Correct 557 ms 3464 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 451 ms 3448 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 18 ms 384 KB Output is correct
10 Correct 470 ms 3416 KB Output is correct
11 Correct 1136 ms 3388 KB Output is correct
12 Correct 722 ms 3540 KB Output is correct
13 Correct 557 ms 3464 KB Output is correct
14 Execution timed out 4014 ms 3792 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 200 ms 3196 KB Output is correct
4 Execution timed out 4037 ms 13296 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 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 18 ms 936 KB Output is correct
8 Correct 18 ms 1024 KB Output is correct
9 Correct 21 ms 1024 KB Output is correct
10 Correct 18 ms 1152 KB Output is correct
11 Correct 19 ms 1024 KB Output is correct
12 Correct 20 ms 1024 KB Output is correct
13 Correct 18 ms 1024 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 755 ms 13040 KB Output is correct
7 Execution timed out 4022 ms 12880 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 72 ms 3192 KB Output is correct
7 Correct 143 ms 4188 KB Output is correct
8 Correct 209 ms 13808 KB Output is correct
9 Correct 266 ms 13424 KB Output is correct
10 Correct 656 ms 13552 KB Output is correct
11 Execution timed out 4035 ms 13424 KB Time limit exceeded
12 Halted 0 ms 0 KB -