Submission #597460

#	Time	Username	Problem	Language	Result	Execution time	Memory
597460		skittles1412	Art Class (IOI13_artclass)	C++17	89 / 100	102 ms	20312 KiB

artclass

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};

int n, m, r[500][500], g[500][500], b[500][500];
bool vis[500][500];

bool ibs(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

bool eq(int a, int b, int x) {
    return abs(a - b) <= x;
}

bool ceq(int x1, int y1, int x2, int y2, int x) {
    return eq(r[x1][y1], r[x2][y2], x) && eq(g[x1][y1], g[x2][y2], x) &&
           eq(b[x1][y1], b[x2][y2], x);
}

int sum(int x, int y) {
    return r[x][y] + g[x][y] + b[x][y];
}

void dfs(int x, int y, int lim) {
    if (vis[x][y]) {
        return;
    }
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i], cy = y + dy[i];
        if (ibs(cx, cy) && ceq(x, y, cx, cy, lim)) {
            dfs(cx, cy, lim);
        }
    }
}

extern "C" int style(int _n,
                     int _m,
                     int _r[500][500],
                     int _g[500][500],
                     int _b[500][500]) {
    n = _n;
    m = _m;
    memcpy(r, _r, sizeof(r));
    memcpy(g, _g, sizeof(g));
    memcpy(b, _b, sizeof(b));
    {
        int xa = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                xa += abs(sum(i, j) - sum(i, j + 1)) +
                      abs(sum(i, j) - sum(i + 1, j));
            }
        }
        double d = double(xa) / (n * m);
        if (d < 17) {
            return 4;
        }
        if (d >= 90) {
            return 3;
        }
    }
    cerr << fixed << setprecision(5);
    auto f1 = [&](int x) -> int {
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                ans += ceq(i, j, i, j + 1, x) + ceq(i + 1, j, i, j, x);
            }
        }
        return ans;
    };
    auto f2 = [&](int x) -> int {
        memset(vis, 0, sizeof(vis));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j]) {
                    ans++;
                    dfs(i, j, x);
                }
            }
        }
        return ans;
    };
    int x2 = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            x2 += sum(i, j) >= 700;
        }
    }
    double d1 = double(f1(10)) / (2 * n * m), d2 = double(x2) / (n * m),
           d3 = double(f2(3)) / (n * m), d4 = double(n * m) / f2(30),
           d5 = double(n * m) / f2(50);
    cerr << d1 << " " << d2 << " " << d3 << " " << d4 << " " << d5 << endl;
    if (d1 > 0.9 || (d1 > 0.5 && d2 > 0.05)) {
        return 1;
    } else {
        return 2;
    }
}

• Subtask 1: 89 / 100