Submission #658311

#	Time	Username	Problem	Language	Result	Execution time	Memory
658311		cristi_a	Art Class (IOI13_artclass)	C++17	87 / 100	104 ms	6376 KiB

artclass

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

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    int area = H * W;

    int nonclr = 0;
    int green = 0;

    int red_sum = 0;
    int green_sum = 0;
    int blue_sum = 0;
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++) {
            int r = R[i][j], g = G[i][j], b = B[i][j];
            if(abs(r-g) < 13 and abs(r-b) < 13 and abs(b-g) < 13) nonclr++;
            if((g-r) + (g-b) >= 20 and g-r > -10 and g-b > -10) green++;

            red_sum += r;
            green_sum += g;
            blue_sum += b;
        }
    double non_color_percent = ((1.00 * nonclr) / (1.00 * area)) * 100.00;
    double green_percent = (1.00 * green) / (1.00 * area) * 100.00;

    static const double sigmaB = 30;
    static const double sigmaN = 65;
    static const int dx[] = {0, 0, -1, 1};
    static const int dy[] = {1, -1, 0, 0};

    auto in = [&](int a, int b) {
        if(a < 0 or a >= H or b < 0 or b >= W) return false;
        return true;
    };

    int noise = 0;
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++)
            for(int k=0; k<4; k++) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if(!in(ni, nj)) continue;

                int difs =  abs(R[i][j] - R[ni][nj]) +
                            abs(G[i][j] - G[ni][nj]) +
                            abs(B[i][j] - B[ni][nj]);
                if(difs >= 200) noise++;
            }
    double noise_percent = 1.00 * noise / (1.00 * area) * 100.00;

    bool viz[500][500];
    auto BFS = [&](double sigma) {
        for(int i=0; i<H; i++)
            for(int j=0; j<W; j++)
                viz[i][j] = false;
        queue<pair<int, int>> q;
        int cnt = 0;
        for(int i=0; i<H; i++)
            for(int j=0; j<W; j++) {
                if(viz[i][j]) continue;

                cnt++;
                q.emplace(i, j);
                viz[i][j] = true;
                while(q.empty() == false) {
                    int x, y; tie(x, y) = q.front(); q.pop();
                    for(int k=0; k<4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if(!in(nx, ny) or viz[nx][ny]) continue;

                        int difr = abs(R[x][y] - R[nx][ny]);
                        int difg = abs(G[x][y] - G[nx][ny]);
                        int difb = abs(R[x][y] - R[nx][ny]);
                        double avg = 1.00 * (difr + difg + difb) / 3.00;
                        if(avg <= sigma) {
                            q.emplace(nx, ny);
                            viz[nx][ny] = true;
                        }
                    }
                }
            }
        return cnt;
    };

    int blocks = BFS(sigmaB);
    int nuances = BFS(sigmaN);

    double red_avg = 1.00 * red_sum / (1.00 * area);
    double blue_avg = 1.00 * blue_sum / (1.00 * area);
    double green_avg = 1.00 * green_sum / (1.00 * area);
    double green_diff_sum = (green_avg - blue_avg) + (green_avg - red_avg);
    //cout << "\ngreen diff sum: " << green_diff_sum << "\n";
    //cout << "noise: " << noise_percent << "\n";


    if(noise_percent <= 1.00) return 4;
    if(noise_percent >= 35.00) return 3;
    if(green_diff_sum >= 20 and noise_percent <= 10.00) return 2;
    return 1;
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:24:12: warning: unused variable 'non_color_percent' [-Wunused-variable]
   24 |     double non_color_percent = ((1.00 * nonclr) / (1.00 * area)) * 100.00;
      |            ^~~~~~~~~~~~~~~~~
artclass.cpp:25:12: warning: unused variable 'green_percent' [-Wunused-variable]
   25 |     double green_percent = (1.00 * green) / (1.00 * area) * 100.00;
      |            ^~~~~~~~~~~~~
artclass.cpp:87:9: warning: unused variable 'blocks' [-Wunused-variable]
   87 |     int blocks = BFS(sigmaB);
      |         ^~~~~~
artclass.cpp:88:9: warning: unused variable 'nuances' [-Wunused-variable]
   88 |     int nuances = BFS(sigmaN);
      |         ^~~~~~~

• Subtask 1: 87 / 100