Submission #768676

#	Time	Username	Problem	Language	Result	Execution time	Memory
768676		boris_mihov	Art Class (IOI13_artclass)	C++17	67 / 100	84 ms	22344 KiB

artclass

#include "artclass.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
 
typedef long long llong;
const int MAXN = 500;
const int INF  = 1e9;
 
struct Cell
{
    int x, y, z;
    friend int operator - (const Cell &a, const Cell &b)
    {
        return abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z);
    }
 
    friend bool operator < (const Cell &a, const Cell &b)
    {
        return (a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z));
    }
};
 
const int BASE3 = 5;
const int BASE4 = 20;
bool close(Cell a, Cell b)
{
    return abs(a.x - b.x) < BASE3 && abs(a.y - b.y) < BASE3 && abs(a.z - b.z) < BASE3;
}
 
bool close2(Cell a, Cell b)
{
    return abs(a.x - b.x) < BASE4 && abs(a.y - b.y) < BASE4 && abs(a.z - b.z) < BASE4;
}
 
const int BASE = 5;
const int BASE2 = 10;
int convert(int x)
{
    if (x % BASE < BASE / 2) return x - (x % BASE);
    return x + BASE - (x % BASE);
}
 
std::set <Cell> s;
Cell pixel[MAXN][MAXN];
Cell block[MAXN][MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
 
bool out(int x, int y)
{
    return (x == -1 || y == -1 || x == MAXN / BASE2 || y == MAXN / BASE2);
}
 
bool outDFS(int x, int y)
{
    return (x == -1 || y == -1 || x == MAXN || y == MAXN);
}
 
bool vis[MAXN][MAXN];
bool vis2[MAXN][MAXN];
void dfs(int x, int y)
{
    vis[x][y] = true;
    for (const auto &[dx, dy] : delta)
    {
        if (outDFS(x + dx, y + dy) || !close(pixel[x][y], pixel[x + dx][y + dy]) || vis[x + dx][y + dy])
        {
            continue;
        }
 
        dfs(x + dx, y + dy);
    }
}
 
void dfs2(int x, int y)
{
    vis2[x][y] = true;
    for (const auto &[dx, dy] : delta)
    {
        if (outDFS(x + dx, y + dy) || !close2(pixel[x][y], pixel[x + dx][y + dy]) || vis2[x + dx][y + dy])
        {
            continue;
        }
 
        dfs2(x + dx, y + dy);
    }
}
 
int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) 
{
    llong sum = 0;
    llong green = 0;
    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            sum += R[i][j];
            sum += G[i][j];
            sum += B[i][j];
            pixel[i][j] = {R[i][j], G[i][j], B[i][j]};
            block[i / BASE2][j / BASE2].x += R[i][j];
            block[i / BASE2][j / BASE2].y += G[i][j];
            block[i / BASE2][j / BASE2].z += B[i][j];
            green += (G[i][j] > 128);
            green -= (B[i][j] > 64 || G[i][j] > 64);
            s.insert({convert(R[i][j]), convert(G[i][j]), convert(B[i][j])});
        }
    }
 
    llong diff = 0;
    llong diff2 = 0;
    for (int i = 0 ; i * BASE2 < MAXN ; ++i)
    {
        for (int j = 0 ; j * BASE2 < MAXN ; ++j)
        {
            for (const auto &[dx, dy] : delta)
            {
                if (out(i + dx, j + dy))
                {
                    continue;
                }
 
                diff += block[i][j] - block[i + dx][j + dy];
            }   
        }
    }
 
    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            for (const auto &[dx, dy] : delta)
            {
                if (out(i + dx, j + dy))
                {
                    continue;
                }
 
                diff2 += pixel[i][j] - pixel[i + dx][j + dy];
            }   
        }
    }
 
    int compCnt = 0;
    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            if (!vis[i][j])
            {
                compCnt++;
                dfs(i, j);
            }
        }
    }
 
    int compCnt2 = 0;
    for (int i = 0 ; i < MAXN ; ++i)
    {
        for (int j = 0 ; j < MAXN ; ++j)
        {
            if (!vis2[i][j])
            {
                compCnt2++;
                dfs2(i, j);
            }
        }
    }
 
    if (compCnt2 < 50) return 4;
    if (compCnt < 50000 && (compCnt > 12000 || compCnt2 > 200)) return 1;
    if (compCnt < 12000 || compCnt2 < 200) return 4;
    if (compCnt2 < 15000) return 2;
    // if (ratio > 0.3) return 2;
    // return 3;
    return 3;
}

• Subtask 1: 67 / 100