Submission #298865

#	Time	Username	Problem	Language	Result	Execution time	Memory
298865		emil_physmath	Art Class (IOI13_artclass)	C++17	43 / 100	2845 ms	4948 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 500;
#ifdef MANSON
mt19937 rng(69420);
#else
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
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 IsSky(int i, int j) {
    int r = R[i][j], g = R[i][j], b = B[i][j];
    return min({r, g, b}) > 100 && max({r, g, b}) > 120;
}
inline bool IsGreen(int i, int j) {
    if (IsSky(i, j)) return true;
    int r = R[i][j], g = R[i][j], b = B[i][j];
    return g >= 80 && g / 1.2 >= min(r, b) && r >= b && max(r, g) / 1.3 > 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()
{
    vector<vector<bool>> ok(n, vector<bool>(m));
    vector<pair<int, int>> comp;
    int comps = 0;
    vector<int> compsz;
    long long sumRecS = 0;
    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);
            sumRecS += recS;
            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();
        }
    if (sumRecS >= 3LL * (n * m)) return 3;
    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;
    if (oks / double(n * m) >= 0.4) return 1;

    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;
    return 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;
}

Compilation message (stderr)

artclass.cpp: In function 'int Solve()':
artclass.cpp:145:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < 6 && i < compsz.size(); ++i)
      |                              ~~^~~~~~~~~~~~~~~

• Subtask 1: 43 / 100