Submission #298682

#	Time	Username	Problem	Language	Result	Execution time	Memory
298682		emil_physmath	Art Class (IOI13_artclass)	C++17	2 / 100	3048 ms	4860 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 500;
#ifdef MANSON
#define BUGO(x) cerr << #x << " = " << x << '\n';
#else
#define BUGO(x)
#endif

int n, m;
int (*R) [500];
int (*G) [500];
int (*B) [500];
const int stCoord = 100;
inline bool OK(int i, int j) {
    return i >= stCoord && i < n && j >= stCoord && j < m;
}

struct Col {
    int r, g, b;
};
inline bool Sim(const Col& l, const Col& r) {
    return abs(l.r - r.r) <= 20 && abs(l.g - r.g) <= 20 && abs(l.b - r.b) <= 20 &&
    abs(l.r - r.r) + abs(l.g - r.g) + abs(l.b - r.b) <= 40;
}
inline bool Sim3(int i, int j, int x, int y) {
    vector<Col> l, r;
    for (int dx = -1; dx <= 1; ++dx)
        for (int dy = -1; dy <= 1; ++dy) {
            int X = i + dx, Y = j + dy;
            if (OK(X, Y))
                l.push_back({R[X][Y], G[X][Y], B[X][Y]});
            X = x + dx, Y = y + dy;
            if (OK(X, Y))
                r.push_back(Col{R[X][Y], G[X][Y], B[X][Y]});
        }
    for (Col& a: l)
        for (Col& b: r)
            if (Sim(a, b))
                return true;
    return false;
}

bool used[maxN][maxN];

void BFS(int i, int j, vector<pair<int, int>>& res)
{
    queue<pair<int, int>> q;
    q.push({i, j});
    while (q.size())
    {
        tie(i, j) = q.front(); q.pop();
        res.push_back({i, j});
        used[i][j] = true;
        for (int di = -1; di <= 1; ++di)
            for (int dj = -1; dj <= 1; ++dj) {
                int x = i + di, y = j + dj;
                if (!OK(x, y) || used[x][y]) continue;
                int diff = 0, ndiff = 0;;
                for (auto [i_, j_]: res) {
                    if (ndiff >= 20 || diff) break;
                    if (!Sim3(i_, j_, x, y)) {
                        ++diff;
                    }
                    else
                        ++ndiff;
                }
                if (diff) continue;
                q.push({x, y});
                used[x][y] = true;
            }
    }
}
bool Is1()
{
    vector<vector<bool>> ok(n, vector<bool>(m));
    vector<pair<int, int>> comp;
    for (int i = stCoord; i + 1 < n; ++i)
        for (int j = stCoord; j + 1 < m; ++j)
        {
            if (used[i][j]) continue;
#ifdef MANSON
            cerr << i << ", " << j << '\n';
#endif
            BFS(i, j, comp);
            int mnX = maxN, mxX = 0, mnY = maxN, mxY = 0;
            unordered_map<int, int> cntx, cnty;
            for (auto& p: comp)
                ++cntx[p.first], ++cnty[p.second];
            for (auto& p: comp) {
                if (cntx[p.first] >= sqrt(comp.size()) / 2) {
                    mnX = min(mnX, p.first);
                    mxX = max(mxX, p.first);
                }
                if (cnty[p.second] >= sqrt(comp.size()) / 2) {
                    mnY = min(mnY, p.second);
                    mxY = max(mxY, p.second);
                }
            }
            int recS = max(1, mxX - mnX + 1) * max(1, mxY - mnY + 1);
            if ((double)comp.size() / recS >= 0.75)
                for (auto [x, y]: comp)
                    ok[x][y] = true;
            BUGO(comp.size())
            BUGO(recS)
            BUGO((double)comp.size() / recS)
            comp.clear();
        }
    int oks = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <m; ++j)
            oks += ok[i][j];
    BUGO(oks)
    BUGO(n * m)
    BUGO(oks / double(n * m))
    return oks / double(n * m) >= 0.4;
}
int style(int n_, int m_, int r_[500][500], int g_[500][500], int b_[500][500]) {
    n = n_, m = m_;
    R = r_, G = g_, B = b_;
    if (Is1()) return 1;
    return 2;
}

• Subtask 1: 2 / 100