oj.uz

Submission #301546

# Submission time Handle Problem Language Result Execution time Memory
301546 2020-09-18T04:14:10 Z kevinsogo Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 3640 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 = 0; 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) or 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 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 0 ms 256 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 1 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 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 21 ms 512 KB Output is correct
7 Correct 526 ms 3464 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 21 ms 384 KB Output is correct
10 Correct 536 ms 3448 KB Output is correct
11 Correct 1188 ms 3576 KB Output is correct
12 Correct 788 ms 3640 KB Output is correct
13 Correct 622 ms 3576 KB Output is correct

Subtask #3
0 / 13.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 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 21 ms 512 KB Output is correct
7 Correct 526 ms 3464 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 21 ms 384 KB Output is correct
10 Correct 536 ms 3448 KB Output is correct
11 Correct 1188 ms 3576 KB Output is correct
12 Correct 788 ms 3640 KB Output is correct
13 Correct 622 ms 3576 KB Output is correct
14 Execution timed out 4019 ms 3448 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 384 KB Output is correct
3 Incorrect 216 ms 3192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
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 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Incorrect 1 ms 384 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 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -