Submission #1155565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155565		alexdd	Art Class (IOI13_artclass)	C++20	34 / 100	59 ms	19272 KiB

artclass

#include "artclass.h"
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int H,W;
int R[505][505],G[505][505],B[505][505];
bool is_green()
{
    int cnt=0;
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            //if(G[i][j] >= max(R[i][j], B[i][j])) cnt++;
            if(2*G[i][j] >= R[i][j] + B[i][j]) cnt++;
        }
    }
    if(cnt*8 >= H*W*7)
        return 1;
    return 0;
}
bool visited[505][505];
int DIFF = 30;
bool similar(int ax, int ay, int bx, int by)
{
    if(abs(R[ax][ay]-R[bx][by]) + abs(G[ax][ay]-G[bx][by]) + abs(B[ax][ay]-B[bx][by]) <= DIFF)
        return 1;
    return 0;
}
int minx,maxx,miny,maxy,cate;
void dfs(int x, int y)
{
    cate++;
    minx = min(minx, x);
    maxx = max(maxx, x);
    miny = min(miny, y);
    maxy = max(maxy, y);
    visited[x][y]=1;
    for(int v=0;v<4;v++)
    {
        int newx = x+dx[v], newy = y+dy[v];
        if(newx>=1 && newx<=H && newy>=1 && newy<=W && !visited[newx][newy] && similar(x,y,newx,newy))
            dfs(newx,newy);
    }
}
int nr_zones(int x)
{
    for(int i=1;i<=H;i++)
        for(int j=1;j<=W;j++)
            visited[i][j]=0;
    DIFF = x;
    int cnt=0;
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            if(!visited[i][j])
            {
                cnt++;
                dfs(i,j);
            }
        }
    }
    return cnt;
}
bool is_squares(int x, int lim, double coef)
{for(int i=1;i<=H;i++)
    for(int j=1;j<=W;j++)
        visited[i][j]=0;
    DIFF = x;
    int rele=0;
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            if(!visited[i][j])
            {
                cate=0;
                minx = maxx = i;
                miny = maxy = j;
                dfs(i,j);
                if((double)((maxx-minx+1)*(maxy-miny+1)) <= (double)cate * coef)
                {

                }
                else
                {
                    rele++;
                }
            }
        }
    }
    return rele <= lim;
}
int style(int cit_H, int cit_W, int cit_R[500][500], int cit_G[500][500], int cit_B[500][500])
{
    H = cit_H;
    W = cit_W;
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            R[i][j] = cit_R[i-1][j-1];
            G[i][j] = cit_G[i-1][j-1];
            B[i][j] = cit_B[i-1][j-1];
        }
    }
    if(is_green()) return 2;
    if(nr_zones(50) <= 100) return 4;
    if(is_squares(10,10,1.5)) return 1;
    if(nr_zones(5)*3 >= H*W *2) return 3;
    return 3;
}

• Subtask 1: 34.2647 / 100