Submission #61287

#	Time	Username	Problem	Language	Result	Execution time	Memory
61287		Eae02	Art Class (IOI13_artclass)	C++14	0 / 100	1479 ms	4704 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;
}

double 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 = 15;
    const Coord deltas[] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    
    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);
            }
        }
    }
    
    uint64_t numOn = 0;
    for (int x = minX; x <= maxX; x++)
    {
        for (int y = minY; y <= maxY; y++)
        {
            if (on[y][x])
                numOn++;
        }
    }
    
    return (double)numOn / ((maxX - minX + 1) * (maxY - minY + 1));
}

bool 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;
    
    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 < 25)
                continue;
            
            double p = squarePercentage(Coord(x, y), H, W, R, G, B);
            if (p < 0.5)
                numNotPassed++;
            else
                numPassed++;
        }
    }
    
    return numPassed > numNotPassed;
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
    if (detectS1(H, W, R, G, B))
        return 1;
    return 2;
}

• Subtask 1: 0 / 100