oj.uz

Submission #301560

# Submission time Handle Problem Language Result Execution time Memory
301560 2020-09-18T04:28:01 Z kevinsogo Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 100676 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;
}



struct Tree {
    int k;
    vector<vector<int>> anc;
    vector<vector<ll>> ancd;
    Tree() {}
    Tree(const vector<int>& par, const vector<ll>& pard) {
        int n = par.size();
        for (k = 0; 1 << k <= n; k++);
        anc = vector<vector<int>>(k, vector<int>(n, -1));
        ancd = vector<vector<ll>>(k, vector<ll>(n, -1));
        anc[0] = par;
        ancd[0] = pard;
        for (int kk = 0; kk < k - 1; kk++) {
            for (int i = 0; i < n; i++) {
                int j = anc[kk][i];
                anc[kk + 1][i] = anc[kk][j];
                ancd[kk + 1][i] = ancd[kk][i] + ancd[kk][j];
            }
        }
    }

    pair<int,ll> walk_up(int i, ll d) {
        for (int kk = k; kk--;) {
            if (d >= ancd[kk][i]) {
                d -= ancd[kk][i];
                i = anc[kk][i];
            }
        }
        return {i, d};
    }
};

vector<int> vals;
Tree rttree, lftree;
void init(int k_, vector<int> r) {
    k = k_;
    n = r.size();
    vals = vector<int>(n);

    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; 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 > 1) {
            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);
                }
            }
        }
    }

    vector<int> lfs(n, -1), rts(n, -1);
    vector<int> wals(n, -1), 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) {
        wals[x] = 0;
        lfs[x] = rts[x] = x;
        for (int i = x - k + 1; i <= x; i++) {
            if (wals[lfs[x]] < wals[mod(i, n)]) lfs[x] = mod(i, n);
        }
        for (int i = x; i < x + k; i++) {
            if (wals[rts[x]] < wals[mod(i, n)]) rts[x] = mod(i, n);
        }
        wals[x] = vals[x];
    }

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

    lftree = Tree(lfs, lfdists);
    rttree = Tree(rts, rtdists);
}

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

bool is_fixed_left(int x, int y) {
    auto [X, rem] = lftree.walk_up(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:62:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int x2 = 0, x1 = cands.size() - 1; x2 < cands.size(); x1 = x2++) {
      |                                             ~~~^~~~~~~~~~~~~~
plants.cpp:89:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for (int x1 = 0, x2 = 1; x2 < bagos.size(); x1++, x2++) {
      |                                      ~~~^~~~~~~~~~~~~~

Subtask #1
5.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 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 70 ms 3192 KB Output is correct
7 Correct 166 ms 11288 KB Output is correct
8 Correct 441 ms 100676 KB Output is correct
9 Correct 503 ms 100420 KB Output is correct
10 Correct 556 ms 100292 KB Output is correct
11 Correct 549 ms 100420 KB Output is correct
12 Correct 559 ms 100292 KB Output is correct
13 Correct 593 ms 100672 KB Output is correct
14 Correct 722 ms 99788 KB Output is correct

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 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 19 ms 640 KB Output is correct
7 Correct 473 ms 5112 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 19 ms 640 KB Output is correct
10 Correct 473 ms 4984 KB Output is correct
11 Correct 348 ms 5112 KB Output is correct
12 Correct 354 ms 5240 KB Output is correct
13 Correct 569 ms 5112 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 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 19 ms 640 KB Output is correct
7 Correct 473 ms 5112 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 19 ms 640 KB Output is correct
10 Correct 473 ms 4984 KB Output is correct
11 Correct 348 ms 5112 KB Output is correct
12 Correct 354 ms 5240 KB Output is correct
13 Correct 569 ms 5112 KB Output is correct
14 Execution timed out 4059 ms 11080 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 111 ms 3792 KB Output is correct
4 Correct 728 ms 100164 KB Output is correct
5 Correct 1079 ms 99916 KB Output is correct
6 Execution timed out 4069 ms 9848 KB Time limit exceeded
7 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 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 1 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 20 ms 1024 KB Output is correct
8 Correct 18 ms 1152 KB Output is correct
9 Correct 20 ms 1024 KB Output is correct
10 Correct 19 ms 1024 KB Output is correct
11 Correct 20 ms 1024 KB Output is correct
12 Correct 24 ms 1016 KB Output is correct
13 Correct 21 ms 1024 KB Output is correct

Subtask #6
0 / 15.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 288 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 828 ms 100048 KB Output is correct
7 Execution timed out 4053 ms 9812 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 384 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 70 ms 3192 KB Output is correct
7 Correct 166 ms 11288 KB Output is correct
8 Correct 441 ms 100676 KB Output is correct
9 Correct 503 ms 100420 KB Output is correct
10 Correct 556 ms 100292 KB Output is correct
11 Correct 549 ms 100420 KB Output is correct
12 Correct 559 ms 100292 KB Output is correct
13 Correct 593 ms 100672 KB Output is correct
14 Correct 722 ms 99788 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 19 ms 640 KB Output is correct
21 Correct 473 ms 5112 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 19 ms 640 KB Output is correct
24 Correct 473 ms 4984 KB Output is correct
25 Correct 348 ms 5112 KB Output is correct
26 Correct 354 ms 5240 KB Output is correct
27 Correct 569 ms 5112 KB Output is correct
28 Execution timed out 4059 ms 11080 KB Time limit exceeded
29 Halted 0 ms 0 KB -