oj.uz

Submission #413601

# Submission time Handle Problem Language Result Execution time Memory
413601 2021-05-29T04:04:51 Z KoD Art Class (IOI13_artclass) C++17
76 / 100
 88 ms 10764 KB 
#include <bits/stdc++.h>
#include "artclass.h"

template <class T> using Vec = std::vector<T>;

struct UnionFind {
    Vec<int> par;
    int comp;
    UnionFind(const int n): par(n, -1), comp(n) {}
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }    
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        comp -= 1;
    }
};

int solve(const int N, const Vec<int> R, const Vec<int> G, const Vec<int> B, const std::array<int, 4> D) {
    UnionFind dsu(N);
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < 4; ++k) {
            const auto j = i + D[k];
            if (0 <= j and j < N) {
                if (std::abs(R[i] - R[j]) <= 20 and std::abs(G[i] - G[j]) <= 20 and std::abs(B[i] - B[j]) <= 20) {
                    dsu.merge(i, j);
                }
            }
        }
    }
    int white = 0, yellow = 0, red = 0;
    for (int i = 0; i < N; ++i) {
        if (R[i] >= 200 and G[i] >= 200 and B[i] >= 200) {
            white += 1;
        }
        if (R[i] >= 200 and G[i] >= 200) {
            yellow += 1;
        }
        if (R[i] >= std::max(G[i], B[i]) + 30) {
            red += 1;
        }
    }
    if ((double) white / N >= 0.3) {
        return 1;
    }
    if ((double) dsu.comp / N >= 0.19) {
        return 3;
    }
    if ((double) dsu.comp / N <= 0.0003) {
        return 4;
    }
    if ((double) white / N >= 0.1 and (double) dsu.comp / N >= 0.1) {
        return 3;
    }
    return 2;
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    const int N = H * W;
    Vec<int> r(N), g(N), b(N);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            r[i * W + j] = R[i][j];
            g[i * W + j] = G[i][j];
            b[i * W + j] = B[i][j];
        }
    }
    return solve(N, r, g, b, std::array<int, 4>{W, 1, -W, -1});
}

Subtask #1
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 9540 KB Output is correct
2 Correct 36 ms 6852 KB Output is correct
3 Incorrect 63 ms 8056 KB Output isn't correct
4 Correct 67 ms 9392 KB Output is correct
5 Incorrect 48 ms 8004 KB Output isn't correct
6 Correct 74 ms 10532 KB Output is correct
7 Correct 49 ms 7748 KB Output is correct
8 Correct 43 ms 5596 KB Output is correct
9 Incorrect 77 ms 10692 KB Output isn't correct
10 Correct 56 ms 9372 KB Output is correct
11 Correct 83 ms 9412 KB Output is correct
12 Correct 46 ms 7556 KB Output is correct
13 Correct 18 ms 2416 KB Output is correct
14 Correct 49 ms 7628 KB Output is correct
15 Correct 60 ms 9324 KB Output is correct
16 Incorrect 41 ms 5956 KB Output isn't correct
17 Correct 63 ms 9176 KB Output is correct
18 Incorrect 67 ms 10052 KB Output isn't correct
19 Correct 35 ms 4396 KB Output is correct
20 Correct 48 ms 7892 KB Output is correct
21 Correct 58 ms 8800 KB Output is correct
22 Correct 65 ms 9800 KB Output is correct
23 Correct 62 ms 9580 KB Output is correct
24 Incorrect 88 ms 9500 KB Output isn't correct
25 Correct 49 ms 6652 KB Output is correct
26 Correct 61 ms 9364 KB Output is correct
27 Incorrect 81 ms 10608 KB Output isn't correct
28 Correct 61 ms 8260 KB Output is correct
29 Correct 66 ms 9556 KB Output is correct
30 Correct 65 ms 8976 KB Output is correct
31 Correct 71 ms 9780 KB Output is correct
32 Correct 42 ms 5660 KB Output is correct
33 Correct 55 ms 7364 KB Output is correct
34 Correct 73 ms 10524 KB Output is correct
35 Incorrect 48 ms 8020 KB Output isn't correct
36 Incorrect 50 ms 8356 KB Output isn't correct
37 Correct 64 ms 9072 KB Output is correct
38 Correct 57 ms 8332 KB Output is correct
39 Correct 76 ms 10544 KB Output is correct
40 Incorrect 66 ms 9000 KB Output isn't correct
41 Correct 56 ms 8332 KB Output is correct
42 Correct 68 ms 8740 KB Output is correct
43 Incorrect 62 ms 9384 KB Output isn't correct
44 Correct 43 ms 5584 KB Output is correct
45 Incorrect 61 ms 9456 KB Output isn't correct
46 Correct 62 ms 8544 KB Output is correct
47 Correct 66 ms 8632 KB Output is correct
48 Correct 59 ms 8408 KB Output is correct
49 Correct 75 ms 10628 KB Output is correct
50 Correct 68 ms 9504 KB Output is correct
51 Correct 63 ms 9132 KB Output is correct
52 Incorrect 52 ms 8476 KB Output isn't correct
53 Correct 42 ms 7276 KB Output is correct
54 Correct 33 ms 4504 KB Output is correct
55 Correct 69 ms 9076 KB Output is correct
56 Correct 19 ms 5020 KB Output is correct
57 Incorrect 73 ms 10728 KB Output isn't correct
58 Correct 63 ms 8828 KB Output is correct
59 Correct 68 ms 10180 KB Output is correct
60 Correct 80 ms 10028 KB Output is correct
61 Correct 58 ms 8584 KB Output is correct
62 Correct 65 ms 9220 KB Output is correct
63 Correct 73 ms 10616 KB Output is correct
64 Correct 66 ms 9300 KB Output is correct
65 Correct 60 ms 8624 KB Output is correct
66 Correct 61 ms 8668 KB Output is correct
67 Correct 60 ms 8384 KB Output is correct
68 Correct 73 ms 10764 KB Output is correct
69 Correct 53 ms 8516 KB Output is correct
70 Correct 57 ms 9176 KB Output is correct
71 Correct 70 ms 10276 KB Output is correct
72 Correct 60 ms 9460 KB Output is correct
73 Incorrect 65 ms 9472 KB Output isn't correct
74 Correct 72 ms 8168 KB Output is correct
75 Correct 47 ms 5740 KB Output is correct
76 Correct 35 ms 4708 KB Output is correct
77 Correct 59 ms 9284 KB Output is correct
78 Incorrect 70 ms 9880 KB Output isn't correct
79 Correct 67 ms 9244 KB Output is correct
80 Correct 58 ms 8204 KB Output is correct
81 Correct 52 ms 6828 KB Output is correct
82 Correct 60 ms 8500 KB Output is correct
83 Incorrect 70 ms 10096 KB Output isn't correct
84 Correct 66 ms 9364 KB Output is correct
85 Correct 60 ms 8644 KB Output is correct
86 Incorrect 77 ms 10564 KB Output isn't correct
87 Correct 62 ms 6852 KB Output is correct
88 Correct 64 ms 9632 KB Output is correct
89 Incorrect 87 ms 9448 KB Output isn't correct
90 Correct 45 ms 7668 KB Output is correct
91 Correct 67 ms 9284 KB Output is correct
92 Correct 68 ms 8240 KB Output is correct
93 Incorrect 73 ms 10564 KB Output isn't correct
94 Correct 60 ms 8516 KB Output is correct
95 Correct 68 ms 9412 KB Output is correct
96 Correct 65 ms 8900 KB Output is correct
97 Correct 46 ms 8000 KB Output is correct
98 Correct 52 ms 6984 KB Output is correct
99 Incorrect 60 ms 9548 KB Output isn't correct
100 Correct 76 ms 10636 KB Output is correct
101 Correct 69 ms 9028 KB Output is correct
102 Correct 74 ms 10432 KB Output is correct