#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 500;
mt19937 rng(2083469420);
inline int rnd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
#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;
}
inline bool IsGreen(int i, int j) {
int r = R[i][j], g = R[i][j], b = B[i][j];
return g + 10 >= max(r, b) && r + 10 >= b && max(r, g) / 1.5 > b;
}
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;
}
}
}
int Solve()
{
int greens = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
greens += IsGreen(i, j);
if (greens >= (n * m) / 2.5)
return 2;
vector<vector<bool>> ok(n, vector<bool>(m));
vector<pair<int, int>> comp;
int comps = 0;
vector<int> compsz;
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
++comps;
BFS(i, j, comp);
compsz.push_back(comp.size());
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))
BUGO("")
BUGO(comps)
sort(compsz.begin(), compsz.end(), greater<int>());
int sumsz = 0;
for (int i = 0; i < 6 && i < compsz.size(); ++i)
sumsz += compsz[i];
BUGO(sumsz)
if (sumsz >= (n * m) * 0.5) return 4;
if (comps >= (n * m) / 150.) return 3;
return oks / double(n * m) >= 0.4 ? 1 : rnd(3, 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_;
return Solve();
// if (Is1()) return 1;
// return 3;
}
