Submission #61390

#	Time	Username	Problem	Language	Result	Execution time	Memory
61390		Eae02	Art Class (IOI13_artclass)	C++14	73 / 100	1188 ms	6920 KiB

artclass

#include "artclass.h"

#include <bits/stdc++.h>

struct Coord
{
    int x, y;
    
    Coord() : x(0), y(0) { }
    Coord(int _x, int _y) : x(_x), y(_y) { }
    
    Coord operator+(Coord other) const
    {
        return Coord(x + other.x, y + other.y);
    }
    
    Coord operator-(Coord other) const
    {
        return Coord(x - other.x, y - other.y);
    }
};

bool inRange(Coord c, int W, int H)
{
    return c.x >= 0 && c.y >= 0 && c.x < W && c.y < H;
}

struct SP
{
    double totPercentage;
    double sqPercentage;
};

SP squarePercentage(Coord c, int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
    std::stack<Coord> stack;
    stack.push(c);
    
    int minX = 500, minY = 500, maxX = 0, maxY = 0;
    bool on[500][500] = { };
    on[c.y][c.x] = true;
    
    const int T = 5;
    const Coord deltas[] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    
    uint64_t numPixels = 0;
    
    while (!stack.empty())
    {
        auto pixel = stack.top();
        stack.pop();
        
        for (Coord d : deltas)
        {
            Coord nPixel = pixel + d;
            if (!inRange(nPixel, W, H) || on[nPixel.y][nPixel.x])
                continue;
            
            int diffR = std::abs(R[pixel.y][pixel.x] - R[nPixel.y][nPixel.x]);
            int diffG = std::abs(G[pixel.y][pixel.x] - G[nPixel.y][nPixel.x]);
            int diffB = std::abs(B[pixel.y][pixel.x] - B[nPixel.y][nPixel.x]);
            int maxDiff = std::max(diffR, std::max(diffG, diffB));
            
            if (maxDiff <= T)
            {
                minX = std::min(minX, nPixel.x);
                maxX = std::max(maxX, nPixel.x);
                minY = std::min(minY, nPixel.y);
                maxY = std::max(maxY, nPixel.y);
                on[nPixel.y][nPixel.x] = true;
                stack.push(nPixel);
                numPixels++;
            }
        }
    }
    
    uint64_t numOn = 0;
    for (int x = minX; x <= maxX; x++)
    {
        for (int y = minY; y <= maxY; y++)
        {
            if (on[y][x])
                numOn++;
        }
    }
    
    SP result;
    result.sqPercentage = (double)numOn / ((maxX - minX + 1) * (maxY - minY + 1));
    result.totPercentage = (double)numPixels / (W * H);
    return result;
}

bool hasWhiteSquare(int H, int W, int R[500][500], int G[500][500], int B[500][500], int minW, int minH)
{
    const int MAX_LIGHTNESS = 175;
    const int MAX_GR_DIFF = 15;
    
    for (int x = 0; x < W - minW; x++)
    {
        for (int y = 0; y < H - minH; y++)
        {
            bool isWhite = true;
            for (int sx = 0; sx < minW && isWhite; sx++)
            {
                for (int sy = 0; sy < minH; sy++)
                {
                    int r = R[y + sy][x + sx];
                    int g = G[y + sy][x + sx];
                    int b = B[y + sy][x + sx];
                    
                    int gr = (r + g + b) / 3;
                    int grDiff = std::max(std::max(std::abs(gr - r), std::abs(gr - b)), std::abs(gr - g));
                    
                    if (grDiff > MAX_GR_DIFF || gr < MAX_LIGHTNESS)
                    {
                        isWhite = false;
                        break;
                    }
                }
            }
            if (isWhite)
                return true;
        }
    }
    return false;
}

int detectS1(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
    const int STEP = 50;
    
    int numPassed = 0;
    int numNotPassed = 0;
    
    double avgPixelCount = 0;
    
    for (int x = STEP / 2; x < W; x += STEP)
    {
        for (int y = STEP / 2; y < H; y += STEP)
        {
            int m = std::max(R[y][x], std::max(G[y][x], B[y][x]));
            if (m < 100)
                continue;
            
            SP p = squarePercentage(Coord(x, y), H, W, R, G, B);
            if (p.sqPercentage < 0.5)
            {
                numNotPassed++;
            }
            else
            {
                numPassed++;
                avgPixelCount += p.totPercentage;
            }
        }
    }
    
    double passedPercent = ((double)numPassed / (numPassed + numNotPassed));
    avgPixelCount /= numPassed;
    
    if (passedPercent > 0.6 && (avgPixelCount > 0.35 || (passedPercent > 0.75 && !hasWhiteSquare(H, W, R, G, B, 35, 35))))
        return 4;
    if (passedPercent > 0.75)
        return 1;
    return -1;
}

const double HALF_ROOT_2 = std::sqrt(2.0) / 2.0;

int detectS1_R45(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
    int hW = W / 2;
    int hH = H / 2;
    auto r45 = [&](Coord c)
    {
        c.x -= hW;
        c.y -= hH;
        Coord newC(std::round(c.x * HALF_ROOT_2 - c.y * HALF_ROOT_2),
                   std::round(c.x * HALF_ROOT_2 + c.y * HALF_ROOT_2));
        return newC + Coord(hW, hH);
    };
    
    int rR[500][500] = {};
    int rG[500][500] = {};
    int rB[500][500] = {};
    
    for (int y = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++)
        {
            Coord src = r45(Coord(x, y));
            if (inRange(src, W, H))
            {
                rR[y][x] = R[src.y][src.x];
                rG[y][x] = G[src.y][src.x];
                rB[y][x] = B[src.y][src.x];
            }
        }
    }
    
    return detectS1(H, W, rR, rG, rB);
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
    int d1 = detectS1(H, W, R, G, B);
    if (d1 != -1)
        return d1;
    d1 = detectS1_R45(H, W, R, G, B);
    if (d1 == 1)
        return 1;
    
    int numGreen = 0;
    
    for (int x = 0; x < W; x++)
    {
        for (int y = 0; y < H; y++)
        {
            int r = R[y][x];
            int g = G[y][x];
            int b = B[y][x];
            
            double pHue;
            if (r > g && r > b)
                pHue = (double)(g - b) / (r - std::min(g, b));
            else if (g > r && g > b)
                pHue =  2.0 + (double)(b - r) / (g - std::min(b, r));
            else if (b > r && b > g)
                pHue = 4.0 + (double)(r - g) / (b - std::min(r, g));
            if (pHue < 0)
                pHue += 360 / 60;
            pHue *= 60;
            
            if (pHue > 60 && pHue < 160)
                numGreen++;
        }
    }
    double pGreen = (double)numGreen / (double)(W * H);
    if (pGreen > 0.2)
        return 2;
    
    return 3;
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:231:22: warning: 'pHue' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 pHue += 360 / 60;
                 ~~~~~^~~~~~~~~~~

• Subtask 1: 73 / 100