Submission #443766

#	Time	Username	Problem	Language	Result	Execution time	Memory
443766		mjhmjh1104	Art Class (IOI13_artclass)	C++17	100 / 100	101 ms	6748 KiB

artclass

#include "artclass.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <numeric>
#include <utility>
using namespace std;

const int DIV = 120;

double averageR, averageG, averageB, deviation, dispersion, grayscale;

const pair<double, double> blue[5] = { { 0, 5.5 }, { 128, 5.5 }, { 128, 29 }, { 0, 29 }, { 0, 5.5 } };
const pair<double, double> red[5] = { { 128, 5.5 }, { 256, 5.5 }, { 256, 29 }, { 128, 29 }, { 128, 5.5 } };

double cross(double x1, double y1, double x2, double y2) {
    return x1 * y2 - x2 * y1;
}

int ccw(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
    double t = cross(b.first - a.first, b.second - a.second, c.first - a.first, c.second - a.second);
    if (t > 0) return 1;
    if (t < 0) return -1;
    return 0;
}

int style(int h, int w, int r[500][500], int g[500][500], int b[500][500]) {
    averageR = accumulate(r[0], r[h - 1] + w, 0LL) / (double)(h * w);
    averageG = accumulate(g[0], g[h - 1] + w, 0LL) / (double)(h * w);
    averageB = accumulate(b[0], b[h - 1] + w, 0LL) / (double)(h * w);
    int rd = min(h, w) / DIV;
    vector<double> v;
    for (int i = 0; i < DIV; i++) for (int j = 0; j < DIV; j++) {
        int x = h * i / DIV, y = w * j / DIV;
        vector<double> _r, _g, _b;
        for (int i = x - rd; i <= x + rd; i++) for (int j = y - rd; j <= y + rd; j++) {
            if (i < 0 || i >= h || j < 0 || j >= w) continue;
            _r.push_back(r[i][j]); _g.push_back(g[i][j]); _b.push_back(b[i][j]);
        }
        double avR = accumulate(_r.begin(), _r.end(), 0.) / (int)_r.size();
        double avG = accumulate(_g.begin(), _g.end(), 0.) / (int)_g.size();
        double avB = accumulate(_b.begin(), _b.end(), 0.) / (int)_b.size();
        for (auto &i: _r) i = (i - avR) * (i - avR);
        for (auto &i: _g) i = (i - avG) * (i - avG);
        for (auto &i: _b) i = (i - avB) * (i - avB);
        v.push_back(accumulate(_r.begin(), _r.end(), 0.) / (int)_r.size());
        v.back() = sqrt(v.back());
        v.push_back(accumulate(_g.begin(), _g.end(), 0.) / (int)_g.size());
        v.back() = sqrt(v.back());
        v.push_back(accumulate(_b.begin(), _b.end(), 0.) / (int)_b.size());
        v.back() = sqrt(v.back());
    }   
    dispersion = accumulate(v.begin(), v.end(), 0.) / (int)v.size();
    grayscale = 0.2989 * averageR + 0.5870 * averageG + 0.1140 * averageB;
    if (dispersion < 5.5) return 4;
    int cnt = 0;
    for (int i = 0; i < 4; i++) cnt += ccw(blue[i], blue[i + 1], pair<int, int>{ grayscale, dispersion });
    if (cnt == 4) return 2;
    cnt = 0;
    for (int i = 0; i < 4; i++) cnt += ccw(red[i], red[i + 1], pair<int, int>{ grayscale, dispersion });
    if (cnt == 4) return 1;
    return 3;
}

• Subtask 1: 100 / 100