Submission #1024886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024886		socpite	Art Class (IOI13_artclass)	C++17	89 / 100	111 ms	51448 KiB

artclass

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

const int blend = 10;

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 freq[3][256];

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;
    memset(freq, 0, sizeof(freq));
    double lowest_fill = 1;
    vector<pair<int, double>> vec;
    double avg[3] = {0, 0, 0};
    double avg_dist[3] = {0, 0, 0};
    int cnt_high[3] = {0, 0, 0};

    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 k = 0; k < 3; k++){
                avg[k] += board[k][i][j];
                freq[k][board[k][i][j]]++;
            }
        }
    }

    for(int k = 0; k < 3; k++){
        avg[k]/=(H*W);
        for(int i = 0; i < 256; i++)if(freq[k][i] >= H*W/256)cnt_high[k]++;
    }
    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);

    // cout << average_contrast << endl;

    if(average_contrast <= 6 && lowest_fill >= 0.9 || average_contrast <= 3)return 4;
    else if(average_contrast >= 23)return 3;
    else if(average_contrast <= 10 || average_contrast <= 12 && max(cnt_high[0], cnt_high[1]) <= 100)return 1;
    else return 2;
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:105:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  105 |     if(average_contrast <= 6 && lowest_fill >= 0.9 || average_contrast <= 3)return 4;
      |        ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
artclass.cpp:107:62: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  107 |     else if(average_contrast <= 10 || average_contrast <= 12 && max(cnt_high[0], cnt_high[1]) <= 100)return 1;
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
artclass.cpp:51:12: warning: unused variable 'avg_dist' [-Wunused-variable]
   51 |     double avg_dist[3] = {0, 0, 0};
      |            ^~~~~~~~

• Subtask 1: 89 / 100