제출 #469661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469661		alextodoran	Art Class (IOI13_artclass)	C++17	98 / 100	103 ms	4464 KiB

artclass

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "artclass.h"

using namespace std;

typedef long long ll;

const int HW_MAX = 500;

struct Color
{
    int R, G, B;
};

Color weed = Color{203, 217, 76};
Color grass = Color{50, 150, 68};
Color sky = Color{180, 211, 217};
Color treeShadow = Color{8, 38, 12};

ll sq (ll a)
{
    if(a < 0)
        return -sqrt(-a);
    return sqrt(a);
}

int dist (Color u, Color v)
{
    int r = abs(u.R - v.R);
    int g = abs(u.G - v.G);
    int b = abs(u.B - v.B);
    return sq((r * r + g * g + b * b) / 3);
}

int getMess (int H, int W, int R[HW_MAX][HW_MAX], int G[HW_MAX][HW_MAX], int B[HW_MAX][HW_MAX])
{
    ll res = 0;
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
        {
            if(i > 0)
            {
                ll val = abs((R[i][j] + G[i][j] + B[i][j]) - (R[i - 1][j] + G[i - 1][j] + B[i - 1][j]));
                res += val;
            }
            if(j > 0)
            {
                ll val = abs((R[i][j] + G[i][j] + B[i][j]) - (R[i][j - 1] + G[i][j - 1] + B[i][j - 1]));
                res += val;
            }
        }
    res /= (H * W);
    return res;
}
int getNature (int H, int W, int R[HW_MAX][HW_MAX], int G[HW_MAX][HW_MAX], int B[HW_MAX][HW_MAX])
{
    ll res = 0;
    for(int i = 0; i < H; i++)
    {
        for(int j = 0; j < W; j++)
        {
            Color col = {R[i][j], G[i][j], B[i][j]};
            int mn = INT_MAX;
            mn = min(mn, dist(weed, col));
            mn = min(mn, dist(grass, col));
            mn = min(mn, dist(sky, col));
            mn = min(mn, dist(treeShadow, col));
            res += mn;
        }
    }
    res /= (H * W);
    return res;
}
int getWhite (int H, int W, int R[HW_MAX][HW_MAX], int G[HW_MAX][HW_MAX], int B[HW_MAX][HW_MAX])
{
    ll res = 0;
    for(int i = 0; i < H; i += 10)
        for(int j = 0; j < W; j += 10)
        {
            int cntAll = 0;
            int cntBad = 0;
            for(int x = i; x < H && x < i + 10; x++)
                for(int y = j; y < W && y < j + 10; y++)
                {
                    cntAll++;
                    int mx = max({R[x][y], G[x][y], B[x][y]});
                    int mn = min({R[x][y], G[x][y], B[x][y]});
                    if(!(mx - mn < 40 && R[x][y] + G[x][y] + B[x][y] > 170 * 3))
                        cntBad++;
                }
            if(100 * cntBad / cntAll < 10)
                res += 1000;
        }
    res /= (H * W / 100);
    return res;
}

int getBlack (int H, int W, int R[HW_MAX][HW_MAX], int G[HW_MAX][HW_MAX], int B[HW_MAX][HW_MAX])
{
    ll res = 0;
    for(int i = 0; i < H; i++)
    {
        for(int j = 0; j < W; j++)
        {
            int mx = max({R[i][j], G[i][j], B[i][j]});
            int mn = min({R[i][j], G[i][j], B[i][j]});
            if(mx - mn < 80 && R[i][j] + G[i][j] + B[i][j] < 40 * 3 && G[i][j] > R[i][j] + 10 && G[i][j] > B[i][j] + 10)
                res += 1000;
        }
    }
    res /= (H * W);
    return res;
}

int di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};

int split (int H, int W, int R[HW_MAX][HW_MAX], int G[HW_MAX][HW_MAX], int B[HW_MAX][HW_MAX])
{
    int CC[HW_MAX][HW_MAX];
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            CC[i][j] = -1;

    int cntCC = 0;

    function <void (int, int)> bfs = [&] (int x, int y)
    {
        queue <pair <int, int>> q;
        CC[x][y] = cntCC - 1;
        q.push(make_pair(x, y));

        while(q.empty() == false)
        {
            pair <int, int> p = q.front();
            q.pop();

            int i = p.first, j = p.second;
            for(int d = 0; d < 4; d++)
            {
                int i1 = i + di[d], j1 = j + dj[d];
                if(0 <= i1 && i1 < H && 0 <= j1 && j1 < W && CC[i1][j1] == -1)
                {
                    int sum = 0;
                    sum += abs(R[i][j] - R[i1][j1]);
                    sum += abs(G[i][j] - G[i1][j1]);
                    sum += abs(B[i][j] - B[i1][j1]);
                    if(sum < 30 * 3)
                    {
                        CC[i1][j1] = CC[i][j];
                        q.push(make_pair(i1, j1));
                    }
                }
            }
        }
    };

    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            if(CC[i][j] == -1)
            {
                cntCC++;
                bfs(i, j);
            }

    return cntCC * 1000 / (H * W);
}

int style (int H, int W, int R[HW_MAX][HW_MAX], int G[HW_MAX][HW_MAX], int B[HW_MAX][HW_MAX])
{
    int mess = getMess(H, W, R, G, B);
    int nature = getNature(H, W, R, G, B);
    int white = getWhite(H, W, R, G, B);
    int black = getBlack(H, W, R, G, B);
    int CCMess = split(H, W, R, G, B);
    if(CCMess > 50)
        return 3;
    if(mess > 160)
        return 3;
    if(nature < 30)
        return 2;
    if(white > 200)
        return 1;
    if(black > 30)
        return 2;
    if(CCMess > 22)
        return 3;
    if(mess + nature > 150)
        return 3;
    if(mess < 20)
        return 4;
    return 2;
}

• Subtask 1: 98 / 100