Submission #61293

#	Time	Username	Problem	Language	Result	Execution time	Memory
61293		Eae02	Art Class (IOI13_artclass)	C++14	8 / 100	1358 ms	7084 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 = 5;
    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 < 100)
                continue;
            
            double p = squarePercentage(Coord(x, y), H, W, R, G, B);
            if (p < 0.5)
                numNotPassed++;
            else
                numPassed++;
        }
    }
    
    const double MIN_PERCENT = 0.75;
    return ((double)numPassed / (numPassed + numNotPassed)) > MIN_PERCENT;
}

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

bool 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 dst = r45(Coord(x, y));
            if (inRange(dst, W, H))
            {
                rR[dst.y][dst.x] = R[y][x];
                rG[dst.y][dst.x] = G[y][x];
                rB[dst.y][dst.x] = B[y][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])
{
    if (detectS1(H, W, R, G, B) || detectS1_R45(H, W, R, G, B))
        return 1;
    return 2;
}

• Subtask 1: 8 / 100