oj.uz

Submission #940623

# Submission time Handle Problem Language Result Execution time Memory
940623 2024-03-07T11:55:17 Z Der_Vlapos Art Class (IOI13_artclass) C++17
0 / 100
 68 ms 31312 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back

#include "artclass.h"

vector<int> dx = {0, 0, 1, -1};
vector<int> dy = {-1, 1, 0, 0};

vector<vector<int>> was, r, g, b;
int n, m;

bool good(int x, int y)
{
    return x >= 0 and y >= 0 and x < n and y < m;
}

int dfs1(int x, int y)
{
    assert(x < n);
    assert(y < m);
    assert(!was[x][y]);
    assert(x >= 0);
    assert(y >= 0);
    was[x][y] = 1;
    int sz = 1;
    for (int d = 0; d < 4; ++d)
    {
        int tox = x + dx[d];
        int toy = y + dy[d];
        if (good(tox, toy) and !was[tox][toy])
        {
            assert(tox < n and toy < m);
            int diff = abs(r[x][y] - r[tox][toy]) + abs(g[x][y] - g[tox][toy]) + abs(b[x][y] - b[tox][toy]);
            if (diff <= 200)
                sz += dfs1(tox, toy);
        }
    }
    return sz;
}

int dfs2(int x, int y)
{
    was[x][y] = 1;
    int sz = 1;
    for (int d = 0; d < 4; ++d)
    {
        int tox = x + dx[d];
        int toy = y + dy[d];
        if (good(tox, toy) and !was[tox][toy])
        {
            int diff = abs(r[x][y] - r[tox][toy]) + abs(g[x][y] - g[tox][toy]) + abs(b[x][y] - b[tox][toy]);
            if (diff <= 60)
                sz += dfs2(tox, toy);
        }
    }
    return sz;
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
    was.resize(H + 100, vector<int>(W + 100));
    r.resize(H + 100, vector<int>(W + 100));
    g.resize(H + 100, vector<int>(W + 100));
    b.resize(H + 100, vector<int>(W + 100));
    n = H;
    m = W;

    vector<int> d;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            r[i][j] = R[i][j];
            g[i][j] = G[i][j];
            b[i][j] = B[i][j];
        }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (!was[i][j])
                d.pb(dfs1(i, j));

    sort(all(d));
    reverse(all(d));
    if ((int)d.size() == 1)
        return 4;
    if (d[0] + d[1] >= (double)(n * m) * 0.60)
        return 4;
    // cout << d[0] << " " << d[1] << ": " << (double)(n * m) * 0.60 << "!\n";
    d.clear();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            was[i][j] = 0;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (!was[i][j])
                d.pb(dfs2(i, j));

    if (((double)d.size() / (double)(H * W)) <= 0.3)
        return 1;
    if (((double)d.size() / (double)(H * W)) >= 0.7)
        return 3;
    return 2;
}

// #include <stdio.h>
// #include "artclass.h"
// #include <assert.h>

// static int DIM[2];
// static int R[500][500];
// static int G[500][500];
// static int B[500][500];

// int main()
// {
//     assert(scanf("%d", &DIM[1]) == 1);
//     assert(scanf("%d", &DIM[0]) == 1);
//     for (int i = 0; i < DIM[0]; i++)
//         for (int j = 0; j < DIM[1]; j++)
//             assert(scanf("%d %d %d", &R[i][j], &G[i][j], &B[i][j]) == 3);
//     printf("%d\n", style(DIM[0], DIM[1], R, G, B));
//     return 0;
// }

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 14940 KB Output isn't correct
2 Correct 68 ms 29424 KB Output is correct
3 Incorrect 35 ms 14416 KB Output isn't correct
4 Incorrect 52 ms 16980 KB Output isn't correct
5 Incorrect 57 ms 19244 KB Output isn't correct
6 Incorrect 50 ms 17744 KB Output isn't correct
7 Incorrect 25 ms 9816 KB Output isn't correct
8 Incorrect 52 ms 17744 KB Output isn't correct
9 Incorrect 54 ms 22940 KB Output isn't correct
10 Correct 48 ms 26208 KB Output is correct
11 Incorrect 40 ms 15800 KB Output isn't correct
12 Incorrect 12 ms 6744 KB Output isn't correct
13 Correct 52 ms 26060 KB Output is correct
14 Correct 29 ms 17232 KB Output is correct
15 Incorrect 33 ms 13732 KB Output isn't correct
16 Incorrect 52 ms 18000 KB Output isn't correct
17 Correct 45 ms 25936 KB Output is correct
18 Correct 50 ms 26316 KB Output is correct
19 Incorrect 55 ms 22796 KB Output isn't correct
20 Incorrect 41 ms 15196 KB Output isn't correct
21 Incorrect 43 ms 16076 KB Output isn't correct
22 Incorrect 44 ms 17840 KB Output isn't correct
23 Incorrect 40 ms 14472 KB Output isn't correct
24 Incorrect 40 ms 15696 KB Output isn't correct
25 Correct 61 ms 31312 KB Output is correct
26 Incorrect 51 ms 19380 KB Output isn't correct
27 Correct 43 ms 18516 KB Output is correct
28 Incorrect 42 ms 17236 KB Output isn't correct
29 Incorrect 48 ms 17192 KB Output isn't correct
30 Incorrect 43 ms 17188 KB Output isn't correct
31 Incorrect 33 ms 14420 KB Output isn't correct
32 Incorrect 29 ms 12380 KB Output isn't correct
33 Incorrect 52 ms 15744 KB Output isn't correct
34 Incorrect 52 ms 19024 KB Output isn't correct
35 Incorrect 46 ms 23392 KB Output isn't correct
36 Incorrect 43 ms 18004 KB Output isn't correct
37 Incorrect 44 ms 16572 KB Output isn't correct
38 Incorrect 40 ms 14652 KB Output isn't correct
39 Incorrect 39 ms 14448 KB Output isn't correct
40 Incorrect 28 ms 9812 KB Output isn't correct
41 Correct 39 ms 21332 KB Output is correct
42 Incorrect 46 ms 23376 KB Output isn't correct
43 Incorrect 33 ms 12112 KB Output isn't correct
44 Incorrect 51 ms 18400 KB Output isn't correct
45 Incorrect 23 ms 9564 KB Output isn't correct
46 Incorrect 44 ms 15508 KB Output isn't correct
47 Incorrect 44 ms 17416 KB Output isn't correct
48 Correct 48 ms 21328 KB Output is correct
49 Correct 14 ms 10332 KB Output is correct
50 Incorrect 24 ms 11124 KB Output isn't correct
51 Incorrect 38 ms 14276 KB Output isn't correct
52 Correct 45 ms 23888 KB Output is correct
53 Incorrect 44 ms 21584 KB Output isn't correct
54 Incorrect 48 ms 14416 KB Output isn't correct
55 Incorrect 41 ms 14416 KB Output isn't correct
56 Incorrect 46 ms 18032 KB Output isn't correct
57 Incorrect 43 ms 14672 KB Output isn't correct
58 Incorrect 34 ms 12244 KB Output isn't correct
59 Incorrect 52 ms 21680 KB Output isn't correct
60 Incorrect 43 ms 17492 KB Output isn't correct
61 Incorrect 33 ms 14412 KB Output isn't correct
62 Correct 45 ms 25952 KB Output is correct
63 Incorrect 41 ms 16912 KB Output isn't correct
64 Incorrect 43 ms 16724 KB Output isn't correct
65 Incorrect 47 ms 16976 KB Output isn't correct
66 Correct 51 ms 28180 KB Output is correct
67 Incorrect 40 ms 16980 KB Output isn't correct
68 Correct 45 ms 25392 KB Output is correct
69 Incorrect 44 ms 15952 KB Output isn't correct
70 Incorrect 40 ms 15956 KB Output isn't correct
71 Incorrect 29 ms 12628 KB Output isn't correct
72 Correct 48 ms 27140 KB Output is correct
73 Correct 33 ms 19796 KB Output is correct
74 Incorrect 41 ms 19284 KB Output isn't correct
75 Incorrect 41 ms 15184 KB Output isn't correct
76 Incorrect 41 ms 16520 KB Output isn't correct
77 Incorrect 55 ms 18380 KB Output isn't correct
78 Incorrect 34 ms 14416 KB Output isn't correct
79 Incorrect 42 ms 15912 KB Output isn't correct
80 Correct 52 ms 13972 KB Output is correct
81 Incorrect 43 ms 16468 KB Output isn't correct
82 Correct 49 ms 27564 KB Output is correct
83 Incorrect 42 ms 19540 KB Output isn't correct
84 Correct 37 ms 21076 KB Output is correct
85 Incorrect 40 ms 15964 KB Output isn't correct
86 Correct 51 ms 28320 KB Output is correct
87 Incorrect 48 ms 15188 KB Output isn't correct
88 Incorrect 30 ms 14672 KB Output isn't correct
89 Incorrect 52 ms 17364 KB Output isn't correct
90 Incorrect 37 ms 17300 KB Output isn't correct
91 Incorrect 39 ms 16468 KB Output isn't correct
92 Incorrect 50 ms 16972 KB Output isn't correct
93 Incorrect 45 ms 17016 KB Output isn't correct
94 Correct 40 ms 22612 KB Output is correct
95 Correct 62 ms 25940 KB Output is correct
96 Incorrect 42 ms 20048 KB Output isn't correct
97 Incorrect 27 ms 11024 KB Output isn't correct
98 Incorrect 34 ms 14428 KB Output isn't correct
99 Correct 39 ms 22876 KB Output is correct
100 Correct 34 ms 20284 KB Output is correct
101 Incorrect 43 ms 16720 KB Output isn't correct
102 Correct 51 ms 26192 KB Output is correct