# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
61380 | Eae02 | 미술 수업 (IOI13_artclass) | C++14 | 1381 ms | 6780 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 = 30;
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, 25, 25))))
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 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])
{
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 d1;
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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |