oj.uz

Submission #491810

# Submission time Handle Problem Language Result Execution time Memory
491810 2021-12-04T14:38:32 Z Lawliet Art Class (IOI13_artclass) C++17
73 / 100
 108 ms 6340 KB 
#include "artclass.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 510;

struct Pixel
{
    int r, g, b;

    Pixel(int red = 0, int green = 0, int blue = 0) 
        : r(red), b(blue), g(green) {}

    int operator - (Pixel a) 
    {
        int diff = abs(r - a.r);
        diff += abs(b - a.b);
        diff += abs(g - a.g);

        return diff;
    }
};

int dx[] = { 0 , 0 , 1 , -1 };
int dy[] = { 1 , -1 , 0 , 0 };

int n, m;

Pixel v[MAXN][MAXN];

bool mark[MAXN][MAXN];

queue<int> q;

int BFS(int x, int y, int w)
{
    int qtd = 0;
    mark[x][y] = true;
    q.push(x); q.push(y);

    while( !q.empty() )
    {
        qtd++;
        int curX = q.front(); q.pop();
        int curY = q.front(); q.pop();

        for(int d = 0 ; d < 4 ; d++)
        {
            int newX = curX + dx[d];
            int newY = curY + dy[d];

            if( 0 >= newX || newX > n )
                continue;

            if( 0 >= newY || newY > m )
                continue;

            if( mark[newX][newY] )
                continue;

            if( v[x][y] - v[newX][newY] > w )
                continue;

            mark[newX][newY] = true;
            q.push(newX); q.push(newY);
        }
    }

    return qtd;
}

int qtdDiff = 0;

int is1or4(int c)
{
    int qtdBad = 0;

    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            bool isBad = false;

            for(int x = max(i - c,0) ; x<= i + c && x <= n ; x++)
                for(int y = max(j - c,0) ; y <= j + c && y <= m ; y++)
                    if( v[i][j] - v[x][y] > 50 ) isBad = true, qtdDiff++;

            if( isBad )
                qtdBad++;
        }
    }

    return qtdBad;
}

int countComponents(int w)
{
    int qtd = 0;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            if( !mark[i][j] ) qtd = max(qtd,BFS(i,j,w));

    return qtd;
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) 
{
    n = H; m = W;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            v[i][j] = Pixel(R[i - 1][j - 1], G[i - 1][j - 1], B[i - 1][j - 1]);

    // is1or4();

    // printf("qtdBad = %d   tamanho = %d     %d\n",is1or4(),n*m,(n*m)/is1or4());
    // printf("componentes = %d\n",(n*m)/countComponents(50));
    // printf("diferentes = %d\n",qtdDiff);

    if( is1or4(1) <= (n*m)/3 )
    {
        if( is1or4(1) <= 10000 )
            return 4;

        return 1;
    }

    qtdDiff = 0;
    is1or4(2);

    int sumGreen = 0, sumRed = 0, sumBlue = 0;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            sumGreen += v[i][j].g, sumRed += v[i][j].r, sumBlue += v[i][j].b;

    sumGreen /= n*m;
    sumRed /= n*m;
    sumBlue /= n*m;

    // printf("r = %d g = %d b = %d\n",sumRed,sumGreen,sumBlue);
    // printf("soma = %d max = %d\n",sumRed+sumBlue+sumGreen,max({sumRed,sumBlue,sumGreen}));

    if( qtdDiff >= 1900000 )
        return 3;

    return 2;
}

Compilation message

artclass.cpp: In constructor 'Pixel::Pixel(int, int, int)':
artclass.cpp:10:15: warning: 'Pixel::b' will be initialized after [-Wreorder]
   10 |     int r, g, b;
      |               ^
artclass.cpp:10:12: warning:   'int Pixel::g' [-Wreorder]
   10 |     int r, g, b;
      |            ^
artclass.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     Pixel(int red = 0, int green = 0, int blue = 0)
      |     ^~~~~

Subtask #1
73.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4792 KB Output is correct
2 Correct 63 ms 6212 KB Output is correct
3 Correct 69 ms 6184 KB Output is correct
4 Correct 41 ms 6216 KB Output is correct
5 Incorrect 58 ms 6216 KB Output isn't correct
6 Incorrect 40 ms 4428 KB Output isn't correct
7 Incorrect 84 ms 5772 KB Output isn't correct
8 Correct 73 ms 5592 KB Output is correct
9 Correct 81 ms 5628 KB Output is correct
10 Correct 54 ms 6236 KB Output is correct
11 Incorrect 91 ms 6220 KB Output isn't correct
12 Correct 62 ms 6148 KB Output is correct
13 Correct 65 ms 6252 KB Output is correct
14 Correct 65 ms 5080 KB Output is correct
15 Correct 38 ms 6236 KB Output is correct
16 Correct 79 ms 5384 KB Output is correct
17 Correct 53 ms 4812 KB Output is correct
18 Correct 41 ms 6212 KB Output is correct
19 Correct 86 ms 5828 KB Output is correct
20 Correct 53 ms 6212 KB Output is correct
21 Correct 79 ms 5700 KB Output is correct
22 Correct 75 ms 5420 KB Output is correct
23 Correct 83 ms 6240 KB Output is correct
24 Correct 80 ms 6212 KB Output is correct
25 Correct 78 ms 5400 KB Output is correct
26 Correct 64 ms 6212 KB Output is correct
27 Correct 87 ms 5600 KB Output is correct
28 Correct 45 ms 6264 KB Output is correct
29 Incorrect 84 ms 6180 KB Output isn't correct
30 Correct 60 ms 6256 KB Output is correct
31 Correct 52 ms 6212 KB Output is correct
32 Correct 50 ms 4832 KB Output is correct
33 Correct 67 ms 5544 KB Output is correct
34 Incorrect 58 ms 6212 KB Output isn't correct
35 Correct 54 ms 6188 KB Output is correct
36 Correct 52 ms 6212 KB Output is correct
37 Correct 75 ms 5600 KB Output is correct
38 Incorrect 80 ms 5444 KB Output isn't correct
39 Incorrect 52 ms 6160 KB Output isn't correct
40 Correct 68 ms 6188 KB Output is correct
41 Correct 60 ms 5060 KB Output is correct
42 Incorrect 42 ms 6248 KB Output isn't correct
43 Correct 83 ms 6212 KB Output is correct
44 Correct 83 ms 5956 KB Output is correct
45 Incorrect 85 ms 5572 KB Output isn't correct
46 Correct 78 ms 5768 KB Output is correct
47 Incorrect 83 ms 5700 KB Output isn't correct
48 Correct 39 ms 4940 KB Output is correct
49 Incorrect 87 ms 5728 KB Output isn't correct
50 Correct 63 ms 6228 KB Output is correct
51 Correct 62 ms 6172 KB Output is correct
52 Correct 77 ms 5588 KB Output is correct
53 Correct 39 ms 6248 KB Output is correct
54 Incorrect 59 ms 5828 KB Output isn't correct
55 Correct 55 ms 6252 KB Output is correct
56 Correct 62 ms 6168 KB Output is correct
57 Correct 61 ms 6008 KB Output is correct
58 Incorrect 42 ms 4524 KB Output isn't correct
59 Correct 51 ms 5644 KB Output is correct
60 Correct 73 ms 6260 KB Output is correct
61 Correct 88 ms 5656 KB Output is correct
62 Correct 87 ms 6172 KB Output is correct
63 Correct 70 ms 6212 KB Output is correct
64 Correct 66 ms 6324 KB Output is correct
65 Incorrect 88 ms 6160 KB Output isn't correct
66 Correct 34 ms 6212 KB Output is correct
67 Correct 66 ms 6256 KB Output is correct
68 Incorrect 45 ms 4556 KB Output isn't correct
69 Correct 55 ms 6236 KB Output is correct
70 Correct 17 ms 6220 KB Output is correct
71 Correct 57 ms 5344 KB Output is correct
72 Incorrect 108 ms 6260 KB Output isn't correct
73 Correct 58 ms 6328 KB Output is correct
74 Correct 62 ms 6156 KB Output is correct
75 Incorrect 78 ms 5676 KB Output isn't correct
76 Incorrect 73 ms 5536 KB Output isn't correct
77 Correct 67 ms 6152 KB Output is correct
78 Correct 75 ms 5724 KB Output is correct
79 Correct 50 ms 6256 KB Output is correct
80 Correct 53 ms 4840 KB Output is correct
81 Correct 42 ms 6256 KB Output is correct
82 Incorrect 22 ms 3952 KB Output isn't correct
83 Correct 82 ms 5808 KB Output is correct
84 Incorrect 57 ms 6212 KB Output isn't correct
85 Correct 53 ms 6208 KB Output is correct
86 Correct 75 ms 6216 KB Output is correct
87 Correct 72 ms 5572 KB Output is correct
88 Correct 65 ms 6268 KB Output is correct
89 Correct 67 ms 5248 KB Output is correct
90 Correct 67 ms 5204 KB Output is correct
91 Correct 67 ms 6240 KB Output is correct
92 Correct 48 ms 6200 KB Output is correct
93 Correct 62 ms 5876 KB Output is correct
94 Correct 69 ms 6340 KB Output is correct
95 Correct 71 ms 6260 KB Output is correct
96 Correct 83 ms 6232 KB Output is correct
97 Incorrect 81 ms 6340 KB Output isn't correct
98 Correct 53 ms 6160 KB Output is correct
99 Correct 63 ms 6140 KB Output is correct
100 Correct 44 ms 6236 KB Output is correct
101 Correct 36 ms 6272 KB Output is correct
102 Correct 74 ms 5700 KB Output is correct