Submission #1024852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024852		vjudge1	Art Class (IOI13_artclass)	C++17	73 / 100	129 ms	50864 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];
        }
    }

    vector<int> all_contrast;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(auto v: mv){
                int nx = i + v.first, ny = j + v.second;
                if(!inb(nx, ny))continue;
                for(int k = 0; k < 3; k++)all_contrast.push_back(abs(board[k][i][j] - board[k][nx][ny]));
            }
        }
    }

    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))});
            }
        }
    }

    double average_contrast = accumulate(all_contrast.begin(), all_contrast.end(), 0)*1.0/all_contrast.size();


    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.9)return 4;
    else if(average_contrast <= 12)return 1;
    else if(average_contrast <= 20)return 2;
    else return 3;
}

• Subtask 1: 73 / 100