제출 #1024823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024823		socpite	미술 수업 (IOI13_artclass)	C++17	23 / 100	54 ms	29524 KiB

artclass

#include "artclass.h"
#include<bits/stdc++.h>
using namespace std;

const int blend = 25;

int vis[505][505];

const pair<int, int> mv[8] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int n, m;
int ccnt;

int mxx, mxy, mnx, mny;

bool inb(int a, int b){
    if(a < 0 || a >= n || b < 0 || b >= m || vis[a][b])return false;
    return true;
}

int board[3][500][500];

void dfs(int x, int y, int cc){
    mxx = max(mxx, x);
    mnx = min(mnx, x);
    mxy = max(mxy, y);
    mny = min(mny, y);
    ccnt++;
    vis[x][y] = cc;
    for(auto v: mv){
        int nx = x + v.first, ny = y + v.second;
        if(!inb(nx, ny))continue;
        bool good = 1;
        for(int i = 0; i < 3; i++){
            if(abs(board[i][x][y] - board[i][nx][ny]) >= blend)good = 0;
        }
        if(good)dfs(nx, ny, cc);
    }
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    int cnt = 0;
    n = H;
    m = W;
    double lowest_fill = 1;
    vector<pair<int, double>> vec;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            vis[i][j] = 0;
            board[0][i][j] = R[i][j];
            board[1][i][j] = G[i][j];
            board[2][i][j] = B[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!vis[i][j]){
                mxx = mnx = i;
                mxy = mny = j;
                ccnt = 0;
                cnt++;
                dfs(i, j, cnt);
                vec.push_back({ccnt, 1.0*ccnt/((mxx-mnx+1)*(mxy - mny + 1))});
            }
        }
    }
    sort(vec.rbegin(), vec.rend());
    while(vec.back().first < 100)vec.pop_back();
    for(auto v: vec)lowest_fill = min(lowest_fill, v.second);
    if(lowest_fill >= 0.99)return 4;
    if(lowest_fill <= 0.1)return 1;
    return 3;
}

• Subtask 1: 23 / 100