Submission #61293

#TimeUsernameProblemLanguageResultExecution timeMemory
61293Eae02Art Class (IOI13_artclass)C++14
8 / 100
1358 ms7084 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...