Submission #491810

#	Time	Username	Problem	Language	Result	Execution time	Memory
491810		Lawliet	Art Class (IOI13_artclass)	C++17	73 / 100	108 ms	6340 KiB

artclass

#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 (stderr)

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 / 100