제출 #102514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102514		naoai	미술 수업 (IOI13_artclass)	C++14	43 / 100	128 ms	6260 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>

using namespace std;

bool style4 (int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    long long val = 0;

    for (int i = 0; i < H; ++ i) {
        int lg = 1;
        for (int j = 1; j < W; ++ j) {
            if (abs(R[i][j] - R[i][j - 1]) <= 20 && abs(G[i][j] - G[i][j - 1]) <= 20 && abs(B[i][j] - B[i][j - 1]) <= 20) {
                ++ lg;
            } else {
                val += 1LL * lg * lg;
                lg = 1;
            }
        }

        val += 1LL * lg * lg;
    }

    if (val > 0.8 * H * W * W) {
        return 1;
    }

    val = 0;
    for (int j = 0; j < W; ++ j) {
        int lg = 1;
        for (int i = 1; i < H; ++ i) {
            if (abs(R[i][j] - R[i - 1][j]) <= 20 && abs(G[i][j] - G[i - 1][j]) <= 20 && abs(B[i][j] - B[i - 1][j]) <= 20) {
                ++ lg;
            } else {
                val += 1LL * lg * lg;
                lg = 1;
            }
        }

        val += 1LL * lg * lg;
    }

    if (val > 0.8 * W * H * H) {
        return 1;
    }
    return 0;
}

bool style2 (int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    int cnt = 0;
    for (int i = 0; i < H; ++ i)
        for (int j = 0; j < W; ++ j) {
            if (G[i][j] > 100)
                ++ cnt;
        }

    if (cnt > 0.25 * H * W)
        return 1;
    return 0;
}

static const int dl[4] = {-1, 0, 0, 1};
static const int dc[4] = {0, -1, 1, 0};
static const int inf = 1 << 30;

bool style1 (int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    vector<vector<bool>> viz(H, vector<bool> (W, 0));

    int whites = 0;
    for (int i = 0; i < H; ++ i)
        for (int j = 0; j < W; ++ j)
            if (R[i][j] > 200 && G[i][j] > 200 && B[i][j] > 200)
                ++ whites;

    if (whites > 0.5 * H * W)
        return 1;

    int total = 0;
    for (int i = 0; i < H; ++ i) {
        for (int j = 0; j < W; ++ j) {
            if (viz[i][j] == 0) {
                queue<pair<int, int>> q;
                q.push({i, j});
                viz[i][j] = 1;

                int xmin = inf, xmax = -inf, ymin = inf, ymax = -inf;
                int cnt = 0;

                while (!q.empty()) {
                    pair<int, int> pos = q.front();
                    q.pop();

                    xmin = min(xmin, pos.first);
                    xmax = max(xmax, pos.first);
                    ymin = min(ymin, pos.second);
                    ymax = max(ymax, pos.second);
                    ++ cnt;

                    for (int dir = 0; dir < 4; ++ dir) {
                        int x = pos.first + dl[dir], y = pos.second + dc[dir];
                        if (0 <= x && x < H && 0 <= y && y < W) {
                            if (viz[x][y] == 0 && abs(R[i][j] - R[x][y]) <= 20 && abs(G[i][j] - G[x][y]) <= 20 && abs(B[i][j] - B[x][y]) <= 20) {
                                viz[x][y] = 1;
                                q.push({x, y});
                            }
                        }
                    }
                }

                bool forma = 0;
                if (cnt > 0.7 * (xmax - xmin + 1) * (ymax - ymin + 1))
                    forma = 1;

                if (forma)
                    total += cnt;
            }
        }
    }

    if (total > 0.5 * H * W)
        return 1;
    return 0;
}


int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    if (style4(H, W, R, G, B))
        return 4;

    if (style1(H, W, R, G, B))
        return 1;

    if (style2(H, W, R, G, B))
        return 2;

    return 3;
}

• Subtask 1: 43 / 100