oj.uz

Submission #768549

# Submission time Handle Problem Language Result Execution time Memory
768549 2023-06-28T09:02:15 Z boris_mihov Art Class (IOI13_artclass) C++17
65 / 100
 98 ms 22356 KB 
#include "artclass.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 500;
const int INF  = 1e9;

struct Cell
{
    int x, y, z;
    friend int operator - (const Cell &a, const Cell &b)
    {
        return abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z);
    }

    friend bool operator < (const Cell &a, const Cell &b)
    {
        return (a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z));
    }
};

const int BASE3 = 5;
const int BASE4 = 20;
bool close(Cell a, Cell b)
{
    return abs(a.x - b.x) < BASE3 && abs(a.y - b.y) < BASE3 && abs(a.z - b.z) < BASE3;
}

bool close2(Cell a, Cell b)
{
    return abs(a.x - b.x) < BASE4 && abs(a.y - b.y) < BASE4 && abs(a.z - b.z) < BASE4;
}

const int BASE = 5;
const int BASE2 = 10;
int convert(int x)
{
    if (x % BASE < BASE / 2) return x - (x % BASE);
    return x + BASE - (x % BASE);
}

std::set <Cell> s;
Cell pixel[MAXN][MAXN];
Cell block[MAXN][MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

bool out(int x, int y)
{
    return (x == -1 || y == -1 || x == MAXN / BASE2 || y == MAXN / BASE2);
}

bool outDFS(int x, int y)
{
    return (x == -1 || y == -1 || x == MAXN || y == MAXN);
}

bool vis[MAXN][MAXN];
bool vis2[MAXN][MAXN];
void dfs(int x, int y)
{
    vis[x][y] = true;
    for (const auto &[dx, dy] : delta)
    {
        if (outDFS(x + dx, y + dy) || !close(pixel[x][y], pixel[x + dx][y + dy]) || vis[x + dx][y + dy])
        {
            continue;
        }

        dfs(x + dx, y + dy);
    }
}

void dfs2(int x, int y)
{
    vis2[x][y] = true;
    for (const auto &[dx, dy] : delta)
    {
        if (outDFS(x + dx, y + dy) || !close2(pixel[x][y], pixel[x + dx][y + dy]) || vis2[x + dx][y + dy])
        {
            continue;
        }

        dfs2(x + dx, y + dy);
    }
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) 
{
    llong sum = 0;
    llong green = 0;
    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            sum += R[i][j];
            sum += G[i][j];
            sum += B[i][j];
            pixel[i][j] = {R[i][j], G[i][j], B[i][j]};
            block[i / BASE2][j / BASE2].x += R[i][j];
            block[i / BASE2][j / BASE2].y += G[i][j];
            block[i / BASE2][j / BASE2].z += B[i][j];
            green += (G[i][j] > 128);
            green -= (B[i][j] > 64 || G[i][j] > 64);
            s.insert({convert(R[i][j]), convert(G[i][j]), convert(B[i][j])});
        }
    }

    llong diff = 0;
    llong diff2 = 0;
    for (int i = 0 ; i * BASE2 < MAXN ; ++i)
    {
        for (int j = 0 ; j * BASE2 < MAXN ; ++j)
        {
            for (const auto &[dx, dy] : delta)
            {
                if (out(i + dx, j + dy))
                {
                    continue;
                }

                diff += block[i][j] - block[i + dx][j + dy];
            }   
        }
    }

    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            for (const auto &[dx, dy] : delta)
            {
                if (out(i + dx, j + dy))
                {
                    continue;
                }

                diff2 += pixel[i][j] - pixel[i + dx][j + dy];
            }   
        }
    }

    int compCnt = 0;
    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            if (!vis[i][j])
            {
                compCnt++;
                dfs(i, j);
            }
        }
    }

    int compCnt2 = 0;
    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            if (!vis2[i][j])
            {
                compCnt2++;
                dfs2(i, j);
            }
        }
    }

    if (compCnt2 < 50) return 4;
    if (compCnt < 60000 && (compCnt > 9000 || compCnt2 > 150)) return 1;
    if (compCnt < 9000 || compCnt2 < 150) return 4;
    if (compCnt2 < 15000) return 2;
    // if (ratio > 0.3) return 2;
    // return 3;
    return 3;
}

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 10528 KB Output isn't correct
2 Correct 65 ms 19800 KB Output is correct
3 Correct 77 ms 22356 KB Output is correct
4 Correct 68 ms 10400 KB Output is correct
5 Correct 70 ms 10244 KB Output is correct
6 Correct 67 ms 14904 KB Output is correct
7 Incorrect 81 ms 7884 KB Output isn't correct
8 Correct 63 ms 13292 KB Output is correct
9 Incorrect 61 ms 15768 KB Output isn't correct
10 Incorrect 98 ms 8916 KB Output isn't correct
11 Correct 59 ms 11968 KB Output is correct
12 Incorrect 68 ms 14716 KB Output isn't correct
13 Correct 65 ms 10144 KB Output is correct
14 Correct 58 ms 16492 KB Output is correct
15 Correct 74 ms 12292 KB Output is correct
16 Incorrect 69 ms 15772 KB Output isn't correct
17 Correct 63 ms 12684 KB Output is correct
18 Correct 76 ms 10180 KB Output is correct
19 Correct 67 ms 9768 KB Output is correct
20 Incorrect 64 ms 16340 KB Output isn't correct
21 Correct 36 ms 18792 KB Output is correct
22 Correct 84 ms 12424 KB Output is correct
23 Correct 74 ms 12420 KB Output is correct
24 Correct 56 ms 14268 KB Output is correct
25 Correct 69 ms 9480 KB Output is correct
26 Correct 52 ms 13320 KB Output is correct
27 Correct 58 ms 15056 KB Output is correct
28 Incorrect 74 ms 12836 KB Output isn't correct
29 Incorrect 54 ms 12836 KB Output isn't correct
30 Correct 74 ms 13956 KB Output is correct
31 Correct 79 ms 8432 KB Output is correct
32 Correct 61 ms 13596 KB Output is correct
33 Correct 60 ms 11796 KB Output is correct
34 Correct 58 ms 18844 KB Output is correct
35 Correct 67 ms 11096 KB Output is correct
36 Incorrect 73 ms 13280 KB Output isn't correct
37 Correct 69 ms 15436 KB Output is correct
38 Incorrect 39 ms 17252 KB Output isn't correct
39 Correct 64 ms 11628 KB Output is correct
40 Correct 72 ms 11660 KB Output is correct
41 Incorrect 61 ms 12584 KB Output isn't correct
42 Correct 53 ms 13516 KB Output is correct
43 Correct 49 ms 14940 KB Output is correct
44 Correct 65 ms 14720 KB Output is correct
45 Incorrect 76 ms 10316 KB Output isn't correct
46 Correct 72 ms 10136 KB Output is correct
47 Incorrect 76 ms 10596 KB Output isn't correct
48 Incorrect 67 ms 10204 KB Output isn't correct
49 Correct 67 ms 10772 KB Output is correct
50 Incorrect 52 ms 13676 KB Output isn't correct
51 Correct 60 ms 10148 KB Output is correct
52 Correct 49 ms 13644 KB Output is correct
53 Correct 77 ms 12424 KB Output is correct
54 Correct 71 ms 10416 KB Output is correct
55 Correct 49 ms 12240 KB Output is correct
56 Correct 74 ms 20192 KB Output is correct
57 Correct 55 ms 15560 KB Output is correct
58 Correct 69 ms 10792 KB Output is correct
59 Correct 76 ms 11212 KB Output is correct
60 Correct 73 ms 14132 KB Output is correct
61 Correct 75 ms 10920 KB Output is correct
62 Correct 63 ms 9916 KB Output is correct
63 Correct 71 ms 11168 KB Output is correct
64 Correct 68 ms 12896 KB Output is correct
65 Correct 66 ms 12508 KB Output is correct
66 Incorrect 85 ms 10572 KB Output isn't correct
67 Correct 65 ms 15380 KB Output is correct
68 Correct 75 ms 10180 KB Output is correct
69 Correct 60 ms 18000 KB Output is correct
70 Correct 88 ms 11548 KB Output is correct
71 Correct 55 ms 13688 KB Output is correct
72 Correct 71 ms 15948 KB Output is correct
73 Correct 58 ms 10536 KB Output is correct
74 Correct 83 ms 10228 KB Output is correct
75 Correct 63 ms 14196 KB Output is correct
76 Incorrect 76 ms 13100 KB Output isn't correct
77 Correct 78 ms 10400 KB Output is correct
78 Incorrect 65 ms 13248 KB Output isn't correct
79 Correct 66 ms 14480 KB Output is correct
80 Correct 75 ms 11456 KB Output is correct
81 Correct 67 ms 14100 KB Output is correct
82 Correct 78 ms 11024 KB Output is correct
83 Correct 65 ms 13736 KB Output is correct
84 Correct 63 ms 18336 KB Output is correct
85 Correct 62 ms 10216 KB Output is correct
86 Correct 81 ms 15132 KB Output is correct
87 Incorrect 80 ms 7504 KB Output isn't correct
88 Incorrect 74 ms 13192 KB Output isn't correct
89 Correct 62 ms 11980 KB Output is correct
90 Incorrect 91 ms 9612 KB Output isn't correct
91 Correct 64 ms 13644 KB Output is correct
92 Correct 58 ms 13532 KB Output is correct
93 Incorrect 76 ms 9328 KB Output isn't correct
94 Correct 68 ms 11828 KB Output is correct
95 Correct 63 ms 16956 KB Output is correct
96 Incorrect 71 ms 15956 KB Output isn't correct
97 Correct 76 ms 11092 KB Output is correct
98 Correct 66 ms 11648 KB Output is correct
99 Correct 55 ms 13488 KB Output is correct
100 Correct 63 ms 16556 KB Output is correct
101 Incorrect 64 ms 16132 KB Output isn't correct
102 Incorrect 66 ms 9956 KB Output isn't correct