oj.uz

Submission #768676

# Submission time Handle Problem Language Result Execution time Memory
768676 2023-06-28T11:25:28 Z boris_mihov Art Class (IOI13_artclass) C++17
67 / 100
 84 ms 22344 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 < 50000 && (compCnt > 12000 || compCnt2 > 200)) return 1;
    if (compCnt < 12000 || compCnt2 < 200) return 4;
    if (compCnt2 < 15000) return 2;
    // if (ratio > 0.3) return 2;
    // return 3;
    return 3;
}

Subtask #1
67.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 13648 KB Output isn't correct
2 Correct 68 ms 9744 KB Output is correct
3 Correct 66 ms 15304 KB Output is correct
4 Correct 69 ms 10340 KB Output is correct
5 Correct 61 ms 19768 KB Output is correct
6 Correct 70 ms 16112 KB Output is correct
7 Correct 58 ms 14100 KB Output is correct
8 Correct 68 ms 11404 KB Output is correct
9 Correct 72 ms 14040 KB Output is correct
10 Correct 69 ms 14836 KB Output is correct
11 Correct 57 ms 10468 KB Output is correct
12 Correct 74 ms 12204 KB Output is correct
13 Correct 84 ms 10208 KB Output is correct
14 Incorrect 75 ms 9392 KB Output isn't correct
15 Incorrect 64 ms 13288 KB Output isn't correct
16 Correct 67 ms 14524 KB Output is correct
17 Correct 52 ms 13388 KB Output is correct
18 Correct 62 ms 16280 KB Output is correct
19 Correct 65 ms 12376 KB Output is correct
20 Incorrect 63 ms 12836 KB Output isn't correct
21 Correct 77 ms 11212 KB Output is correct
22 Correct 54 ms 16636 KB Output is correct
23 Correct 50 ms 13792 KB Output is correct
24 Correct 66 ms 11000 KB Output is correct
25 Correct 59 ms 11736 KB Output is correct
26 Correct 62 ms 12448 KB Output is correct
27 Correct 60 ms 12080 KB Output is correct
28 Correct 76 ms 10496 KB Output is correct
29 Correct 60 ms 14192 KB Output is correct
30 Incorrect 72 ms 13216 KB Output isn't correct
31 Correct 57 ms 11992 KB Output is correct
32 Correct 63 ms 12680 KB Output is correct
33 Correct 62 ms 9900 KB Output is correct
34 Incorrect 49 ms 14268 KB Output isn't correct
35 Incorrect 62 ms 12552 KB Output isn't correct
36 Correct 59 ms 10140 KB Output is correct
37 Correct 65 ms 11936 KB Output is correct
38 Correct 72 ms 11672 KB Output is correct
39 Incorrect 40 ms 17280 KB Output isn't correct
40 Correct 64 ms 13008 KB Output is correct
41 Correct 50 ms 13388 KB Output is correct
42 Correct 57 ms 16380 KB Output is correct
43 Correct 54 ms 13644 KB Output is correct
44 Correct 52 ms 14924 KB Output is correct
45 Correct 64 ms 14764 KB Output is correct
46 Correct 44 ms 15168 KB Output is correct
47 Correct 79 ms 11084 KB Output is correct
48 Correct 62 ms 10396 KB Output is correct
49 Incorrect 65 ms 10544 KB Output isn't correct
50 Correct 38 ms 18924 KB Output is correct
51 Incorrect 68 ms 10632 KB Output isn't correct
52 Incorrect 70 ms 11576 KB Output isn't correct
53 Incorrect 73 ms 9536 KB Output isn't correct
54 Correct 72 ms 10128 KB Output is correct
55 Incorrect 67 ms 10200 KB Output isn't correct
56 Incorrect 62 ms 16052 KB Output isn't correct
57 Correct 70 ms 15940 KB Output is correct
58 Correct 76 ms 12380 KB Output is correct
59 Correct 65 ms 10140 KB Output is correct
60 Incorrect 77 ms 7468 KB Output isn't correct
61 Correct 49 ms 12332 KB Output is correct
62 Correct 60 ms 13728 KB Output is correct
63 Correct 68 ms 22344 KB Output is correct
64 Incorrect 75 ms 8916 KB Output isn't correct
65 Correct 57 ms 18832 KB Output is correct
66 Incorrect 74 ms 7940 KB Output isn't correct
67 Correct 73 ms 12420 KB Output is correct
68 Correct 66 ms 10796 KB Output is correct
69 Correct 75 ms 14112 KB Output is correct
70 Incorrect 74 ms 10136 KB Output isn't correct
71 Correct 58 ms 11676 KB Output is correct
72 Correct 58 ms 17036 KB Output is correct
73 Incorrect 74 ms 13120 KB Output isn't correct
74 Correct 76 ms 10188 KB Output is correct
75 Correct 54 ms 13536 KB Output is correct
76 Correct 48 ms 13544 KB Output is correct
77 Correct 61 ms 10144 KB Output is correct
78 Correct 72 ms 20172 KB Output is correct
79 Correct 77 ms 15212 KB Output is correct
80 Correct 48 ms 13320 KB Output is correct
81 Correct 70 ms 15452 KB Output is correct
82 Incorrect 52 ms 12844 KB Output isn't correct
83 Correct 72 ms 10208 KB Output is correct
84 Correct 72 ms 10916 KB Output is correct
85 Correct 53 ms 13452 KB Output is correct
86 Incorrect 70 ms 13328 KB Output isn't correct
87 Correct 75 ms 11108 KB Output is correct
88 Incorrect 65 ms 9976 KB Output isn't correct
89 Incorrect 63 ms 15756 KB Output isn't correct
90 Correct 54 ms 14824 KB Output is correct
91 Correct 58 ms 18408 KB Output is correct
92 Correct 61 ms 17988 KB Output is correct
93 Correct 56 ms 15608 KB Output is correct
94 Correct 78 ms 10496 KB Output is correct
95 Incorrect 73 ms 10504 KB Output isn't correct
96 Correct 65 ms 8428 KB Output is correct
97 Correct 67 ms 10744 KB Output is correct
98 Correct 60 ms 13632 KB Output is correct
99 Incorrect 58 ms 15868 KB Output isn't correct
100 Correct 63 ms 11636 KB Output is correct
101 Correct 67 ms 9416 KB Output is correct
102 Correct 73 ms 10988 KB Output is correct