oj.uz

Submission #768668

# Submission time Handle Problem Language Result Execution time Memory
768668 2023-06-28T10:59:15 Z boris_mihov Art Class (IOI13_artclass) C++17
62 / 100
 148 ms 31992 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 CNTBASE = 7;
int compBase[CNTBASE] = {2, 5, 10, 15, 20, 50, 100};
bool close(Cell a, Cell b, int idx)
{
    return abs(a.x - b.x) < compBase[idx] && abs(a.y - b.y) < compBase[idx] && abs(a.z - b.z) < compBase[idx];
}

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][CNTBASE];
void dfs(int x, int y, int cnt)
{
    vis[x][y][cnt] = true;
    for (const auto &[dx, dy] : delta)
    {
        if (outDFS(x + dx, y + dy) || !close(pixel[x][y], pixel[x + dx][y + dy], cnt) || vis[x + dx][y + dy][cnt])
        {
            continue;
        }

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

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[CNTBASE];
    for (int k = 0 ; k < CNTBASE ; ++k)
    {
        compCnt[k] = 0;
        for (int i = 0 ; i < MAXN ; ++i)
        {
            for (int j = 0 ; j < MAXN ; ++j)
            {
                if (!vis[i][j][k])
                {
                    compCnt[k]++;
                    dfs(i, j, k);
                }
            }
        }
    }

    for (int i = 0 ; i < CNTBASE ; ++i)
    {
        std::cerr << compCnt[i] << ' ';
    }

    std::cerr << '\n';
    if (compCnt[6] > 20) return 3;
    if (compCnt[6] <= 3 && compCnt[4] < 50) return 4;
    if (compCnt[1] < 60000 && (compCnt[1] > 9000 || compCnt[4] > 150)) return 1;
    if ((compCnt[1] < 9000 || compCnt[4] < 150)) return 4;
    if (compCnt[4] < 15000) return 2;
    return 3;
}

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 30528 KB Output is correct
2 Correct 110 ms 27880 KB Output is correct
3 Correct 123 ms 29748 KB Output is correct
4 Incorrect 132 ms 31144 KB Output isn't correct
5 Incorrect 123 ms 27736 KB Output isn't correct
6 Correct 119 ms 29772 KB Output is correct
7 Correct 123 ms 31620 KB Output is correct
8 Correct 123 ms 30688 KB Output is correct
9 Correct 109 ms 25860 KB Output is correct
10 Incorrect 122 ms 29172 KB Output isn't correct
11 Correct 122 ms 27248 KB Output is correct
12 Correct 100 ms 28928 KB Output is correct
13 Correct 101 ms 19692 KB Output is correct
14 Correct 139 ms 31664 KB Output is correct
15 Correct 111 ms 26400 KB Output is correct
16 Correct 132 ms 31500 KB Output is correct
17 Correct 114 ms 31576 KB Output is correct
18 Correct 102 ms 25472 KB Output is correct
19 Correct 121 ms 25572 KB Output is correct
20 Correct 118 ms 24404 KB Output is correct
21 Correct 120 ms 31756 KB Output is correct
22 Correct 110 ms 21568 KB Output is correct
23 Correct 124 ms 28636 KB Output is correct
24 Correct 121 ms 25520 KB Output is correct
25 Correct 97 ms 21840 KB Output is correct
26 Incorrect 123 ms 28120 KB Output isn't correct
27 Incorrect 118 ms 28912 KB Output isn't correct
28 Correct 111 ms 31820 KB Output is correct
29 Correct 129 ms 31524 KB Output is correct
30 Correct 138 ms 27520 KB Output is correct
31 Correct 119 ms 29900 KB Output is correct
32 Incorrect 121 ms 24376 KB Output isn't correct
33 Correct 99 ms 22428 KB Output is correct
34 Incorrect 124 ms 30260 KB Output isn't correct
35 Correct 117 ms 27504 KB Output is correct
36 Correct 117 ms 26644 KB Output is correct
37 Correct 102 ms 20592 KB Output is correct
38 Correct 127 ms 26640 KB Output is correct
39 Incorrect 107 ms 21500 KB Output isn't correct
40 Incorrect 123 ms 23080 KB Output isn't correct
41 Correct 116 ms 26288 KB Output is correct
42 Correct 127 ms 30360 KB Output is correct
43 Correct 128 ms 26672 KB Output is correct
44 Correct 106 ms 27212 KB Output is correct
45 Correct 128 ms 27852 KB Output is correct
46 Correct 132 ms 23964 KB Output is correct
47 Correct 127 ms 25336 KB Output is correct
48 Correct 106 ms 28484 KB Output is correct
49 Correct 117 ms 28540 KB Output is correct
50 Correct 138 ms 30664 KB Output is correct
51 Incorrect 113 ms 27212 KB Output isn't correct
52 Correct 123 ms 28364 KB Output is correct
53 Incorrect 126 ms 31816 KB Output isn't correct
54 Correct 124 ms 30692 KB Output is correct
55 Incorrect 112 ms 27084 KB Output isn't correct
56 Correct 109 ms 31288 KB Output is correct
57 Correct 114 ms 29960 KB Output is correct
58 Correct 118 ms 31696 KB Output is correct
59 Correct 106 ms 27736 KB Output is correct
60 Correct 129 ms 29804 KB Output is correct
61 Correct 148 ms 30156 KB Output is correct
62 Correct 108 ms 31560 KB Output is correct
63 Incorrect 109 ms 20000 KB Output isn't correct
64 Incorrect 137 ms 27632 KB Output isn't correct
65 Correct 118 ms 31624 KB Output is correct
66 Correct 110 ms 29644 KB Output is correct
67 Correct 100 ms 21836 KB Output is correct
68 Correct 108 ms 25664 KB Output is correct
69 Correct 128 ms 23792 KB Output is correct
70 Correct 129 ms 30288 KB Output is correct
71 Correct 124 ms 26488 KB Output is correct
72 Incorrect 117 ms 28620 KB Output isn't correct
73 Incorrect 122 ms 28604 KB Output isn't correct
74 Incorrect 111 ms 24280 KB Output isn't correct
75 Correct 123 ms 29424 KB Output is correct
76 Correct 125 ms 29600 KB Output is correct
77 Correct 116 ms 31692 KB Output is correct
78 Correct 127 ms 31436 KB Output is correct
79 Incorrect 124 ms 27468 KB Output isn't correct
80 Correct 111 ms 26800 KB Output is correct
81 Correct 117 ms 24344 KB Output is correct
82 Correct 116 ms 27212 KB Output is correct
83 Correct 107 ms 22568 KB Output is correct
84 Incorrect 112 ms 24872 KB Output isn't correct
85 Incorrect 102 ms 27076 KB Output isn't correct
86 Correct 111 ms 27860 KB Output is correct
87 Incorrect 125 ms 23628 KB Output isn't correct
88 Incorrect 129 ms 28104 KB Output isn't correct
89 Correct 127 ms 31716 KB Output is correct
90 Correct 121 ms 31992 KB Output is correct
91 Correct 122 ms 28316 KB Output is correct
92 Correct 115 ms 21876 KB Output is correct
93 Correct 143 ms 24844 KB Output is correct
94 Incorrect 115 ms 27980 KB Output isn't correct
95 Correct 123 ms 30040 KB Output is correct
96 Correct 116 ms 29108 KB Output is correct
97 Incorrect 121 ms 27832 KB Output isn't correct
98 Correct 104 ms 31700 KB Output is correct
99 Incorrect 125 ms 27768 KB Output isn't correct
100 Correct 119 ms 29612 KB Output is correct
101 Incorrect 114 ms 31780 KB Output isn't correct
102 Incorrect 115 ms 29340 KB Output isn't correct