Submission #280406

#	Time	Username	Problem	Language	Result	Execution time	Memory
280406		Kastanda	Art Class (IOI13_artclass)	C++11	93 / 100	106 ms	15736 KiB

artclass

// M
#include<bits/stdc++.h>
#include "artclass.h"
#define ID(i, j) ((i) * (m) + (j))
using namespace std;
const int N = 505, MXN = N * N;
int n, m, R[N][N], G[N][N], B[N][N];
bool MR[MXN];
vector < int > Adj[MXN];

int SZ = 30, DF = 70;
vector < int > IGNORE = {0, 0, 0};

inline vector < int > GetMean(int i, int j)
{
        int cnt = 0;
        vector < int > Rs(3, 0);
        for (int dx = 0; dx < SZ; dx ++)
                for (int dy = 0; dy < SZ; dy ++)
                        if (i + dx >= 0 && i + dx < n && j + dy >= 0 && j + dy < m)
                        {
                                Rs[0] += R[i + dx][j + dy];
                                Rs[1] += G[i + dx][j + dy];
                                Rs[2] += B[i + dx][j + dy];
                                cnt ++;
                        }
        for (int i = 0; i < 3; i ++)
                Rs[i] /= cnt;

        for (int i = 0; i < 3; i ++)
                if (IGNORE[i])
                        Rs[i] = 0;

        return Rs;
}

inline bool Similar(int i1, int j1, int i2, int j2)
{
        vector < int > X = GetMean(i1, j1);//{R[i1][j1], B[i1][j1], G[i1][j1]};
        vector < int > Y = GetMean(i2, j2);//{R[i2][j2], B[i2][j2], G[i2][j2]};

        for (int i = 0; i < 3; i ++)
                if (abs(X[i] - Y[i]) > DF)
                        return 0;

        return 1;
}
inline void MakeGraph()
{
        for (int i = 0; i < n; i += SZ)
                for (int j = 0; j < m; j += SZ)
                {
                        if (i + SZ < n && Similar(i, j, i + SZ, j))
                        {
                                Adj[ID(i / SZ, j / SZ)].push_back(ID(i / SZ + 1, j / SZ));
                                Adj[ID(i / SZ + 1, j / SZ)].push_back(ID(i / SZ, j / SZ));
                        }
                        if (j + SZ < m && Similar(i, j, i, j + SZ))
                        {
                                Adj[ID(i / SZ, j / SZ)].push_back(ID(i / SZ, j / SZ + 1));
                                Adj[ID(i / SZ, j / SZ + 1)].push_back(ID(i / SZ, j / SZ));
                        }
                }
}
void DFS(int v)
{
        MR[v] = 1;
        for (int u : Adj[v])
                if (!MR[u]) DFS(u);
}
double CountComps(int _sz = 10, int _df = 70, vector < int > _ignore = {0, 0, 0})
{
        SZ = _sz;
        DF = _df;
        IGNORE = _ignore;

        MakeGraph();
        int cp = 0;
        for (int i = 0; i < n; i += SZ)
                for (int j = 0; j < m; j += SZ)
                        if (!MR[ID(i / SZ, j / SZ)])
                                DFS(ID(i / SZ, j / SZ)), cp ++;

        memset(MR, 0, sizeof(MR));
        for (int i = 0; i < n; i += SZ)
                for (int j = 0; j < m; j += SZ)
                        Adj[ID(i / SZ, j / SZ)].clear();

        double rs = (double)cp / (double)n / (double)m;
        rs *= 1e5;

        return rs;
}
double GreenShift(int _sz = 10, double leg = 0.0, double rig = 0.4)
{
        SZ = _sz;
        IGNORE = {0, 0, 0};

        int cnt = 1;
        double totg = 0;
        for (int i = 0; i < n; i += SZ)
                for (int j = 0; j < m; j += SZ)
                {
                        vector < int > X = GetMean(i, j);
                        double g = (double)X[1] / (double)(X[0] + X[1] + X[2]);
                        if (g >= leg && g <= rig)
                                continue;
                        totg += g; cnt ++;
                }
        totg /= (double)cnt;
        return totg;
}
double WhiteShift(int _sz = 10, int MXDF = 100, int GREY = 190)//double lew = 0.0, double riw = 0.4)
{
        SZ = _sz;
        IGNORE = {0, 0, 0};

        int cnt = 1, cnt2 = 1;
        for (int i = 0; i < n; i += SZ)
                for (int j = 0; j < m; j += SZ)
                {
                        vector < int > X = GetMean(i, j);
                        int mxdf = max({X[0], X[1], X[2]}) - min({X[0], X[1], X[2]});
                        if (mxdf > MXDF || max({X[0], X[1], X[2]}) <= GREY)
                                cnt ++;
                        else
                                cnt2 ++;
                }
        double rat = (double)cnt / (double)cnt2;
        return rat;
}
int Style()
{
        vector < double > Grad(5, 0);

        double cp1 = CountComps(7, 20, {1, 0, 1});

        if (cp1 <= 10) // Magnitude of 22,000
        {
                Grad[3] = -1e14;
                Grad[4] += exp((30 - cp1) / 2);
        }
        double cp2 = CountComps(7, 20, {0, 0, 1});

//      cout << cp1 << " :: " << cp2 << endl;


        if (cp2 <= 10) // Magnitude of 22,000
        {
                Grad[3] = -1e14;
                Grad[4] += exp((30 - cp2) / 2);
        }
        if (cp1 >= 10 && cp2 >= 10)
                Grad[4] = -1e14;

        if (cp1 <= 100 || cp2 <= 100)
                Grad[3] = -1e14;

        //cout << cp1 << " :: " << cp2 << endl;

        //if (cp1 <= 20 && cp2 <= 20 && cp1 + cp2 <= 29)
                //return 4;

        double cp = CountComps(7, 10, {0, 1, 1});

        //cout << cp << endl;

        if (cp <= 70)
                Grad[2] = -1e14;
        if (cp <= 400)
                Grad[3] = -1e14;
        if (cp >= 100)
                Grad[4] = -1e14;

        double gr = GreenShift(20, 0.0, 0.4);

        if (gr < 0.2)
        {
                Grad[3] += exp((20 - gr * 100) / 2);
                Grad[4] += exp((20 - gr * 100) / 3);
                //return 3;
        }

        if (gr > 0.3)
        {
                Grad[1] += exp(((gr - 0.3) * 100) / 2);
                Grad[2] += exp(((gr - 0.3) * 100) / 2);
        }

        double wt = WhiteShift(5, 40, 130);

        if (wt < 3.0)
        {
                Grad[4] = -1e9;
                Grad[3] += exp((20 - wt * 20.0/3.0) / 2);
                Grad[1] += exp((20 - wt * 20.0/3.0) / 2);
        }

        /*for (int i = 1; i <= 4; i ++)
                cout << Grad[i] << " : ";
        cout << endl;*/

        double Mx = -1e18;
        for (int i = 1; i <= 4; i ++)
                Mx = max(Mx, Grad[i]);

        if (Mx == Grad[3])
                return 3;
        if (Mx == Grad[4])
                return 4;

        gr = GreenShift(20, 0.2, 0.4);

//      cout << gr << endl;

//      cout << wt << endl;

//      if (wt >= 3)
//              return 2;
        if (Grad[1] > Grad[2])
                return 1;

        return 2;
}
int style(int _n, int _m, int _R[500][500], int _G[500][500], int _B[500][500])
{
        n = _n; m = _m;
        for (int i = 0; i < n; i ++)
                for (int j = 0; j < m; j ++)
                        R[i][j] = _R[i][j], G[i][j] = _G[i][j], B[i][j] = _B[i][j];

        return Style();
}

• Subtask 1: 93 / 100