Submission #1784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1784		kriii	Art Class (IOI13_artclass)	C++98	100 / 100	188 ms	6316 KiB

artclass

#include "artclass.h"
#include <math.h>
#define suff 0.85

bool sim(double r1, double g1, double b1, double r2, double g2, double b2, int v)
{
	return (r1 - r2) * (r1 - r2) + (b1 - b2) * (b1 - b2) + (g1 - g2) * (g1 - g2) <= v;
}

int chk[500][500]; int X[250000],Y[250000];

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
	int i,j,k; double r,g,b,hor,ver;

	ver = 0;
	for (i=0;i<H;i++){
		r = g = b = 0;
		for (j=0;j<W;j++){
			r += R[i][j];
			g += G[i][j];
			b += B[i][j];
		}
		r /= W; g /= W; b /= W;
		
		hor = 0;
		for (j=0;j<W;j++){
			if (sim(r,g,b,R[i][j],G[i][j],B[i][j],2700)) hor++;
		}
		hor /= W;
		if (hor >= suff) ver++;
	}
	ver /= H;
	if (ver >= suff) return 4;

	ver = 0;
	for (j=0;j<W;j++){
		r = g = b = 0;
		for (i=0;i<H;i++){
			r += R[i][j];
			g += G[i][j];
			b += B[i][j];
		}
		r /= W; g /= W; b /= W;
		
		hor = 0;
		for (i=0;i<H;i++){
			if (sim(r,g,b,R[i][j],G[i][j],B[i][j],2700)) hor++;
		}
		hor /= H;
		if (hor >= suff) ver++;
	}
	ver /= W;
	if (ver >= suff) return 4;

	for (i=0;i<H;i++) for (j=0;j<W;j++){
		chk[i][j] = 0;
	}
	
	int c = 0,head,tail,small=0;
	double max = 0;

	for (i=0;i<H;i++) for (j=0;j<W;j++) if (chk[i][j] == 0){
		head = -1, tail = -1;
		int x, y, px, py; c++;
		int dx[8] = {0,1,0,-1,1,-1,1,-1};
		int dy[8] = {1,0,-1,0,1,1,-1,-1};
		++head; X[head] = i; Y[head] = j; chk[i][j] = c;
		while (tail < head){
			++tail; x = X[tail]; y = Y[tail];
			for (k=0;k<8;k++){
				px = x + dx[k];
				py = y + dy[k];
				if (px < 0 || px >= H || py < 0 || py >= W) continue;
				if (sim(R[x][y],G[x][y],B[x][y],R[px][py],G[px][py],B[px][py],1200) && chk[px][py] != c){
					++head; X[head] = px; Y[head] = py; chk[px][py] = c;
				}
			}
		}
		if (max < head) max = head;
		if (head < 50) small++;
	}
	max /= H * W;
	if (max >= 0.90) return 2;
	if (c >= 5000) return 3;
    return 1;
}

• Subtask 1: 100 / 100