Submission #94198

#	Time	Username	Problem	Language	Result	Execution time	Memory
94198		fjzzq2002	Art Class (IOI13_artclass)	C++14	100 / 100	87 ms	12152 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
typedef double ld;
struct pnt{int x,y,z;};
pnt operator + (pnt a,pnt b)
{return pnt{a.x+b.x,a.y+b.y,a.z+b.z};}
ld sqr(ld x) {return x*x;}
ld dis(pnt a,pnt b)
{return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)+sqr(a.z-b.z));}
pnt u[500][500],p[100][100];
int ff[999999],cn[999999];
int gf(int x) {return (~ff[x])?ff[x]=gf(ff[x]):x;}
void uni(int a,int b)
{
	a=gf(a),b=gf(b);
	if(a!=b) ff[a]=b;
}
int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
	for(int i=0;i<H;++i)
		for(int j=0;j<W;++j)
			u[i][j]=pnt{R[i][j],G[i][j],B[i][j]};
	int HH=H/5,WW=W/5;
	for(int i=0;i<HH;++i)
		for(int j=0;j<WW;++j)
		{
			for(int x=0;x<5;++x)
				for(int y=0;y<5;++y)
					p[i][j]=p[i][j]+u[i*5+x][j*5+y];
			p[i][j].x/=25,
			p[i][j].y/=25,
			p[i][j].z/=25;
		}
	ld V0,V10,V11;
	{
	int s0=0; ld s1=0;
	for(int i=0;i<HH;++i)
		for(int j=0;j<WW;++j)
			s1+=p[i][j].x,++s0;
	V0=s1/s0;
	}
	{
	memset(ff,-1,sizeof ff);
	for(int i=0;i<H;++i)
		for(int j=0;j+1<W;++j)
			if(dis(u[i][j],u[i][j+1])<30)
				uni(i*W+j,i*W+j+1);
	for(int i=0;i+1<H;++i)
		for(int j=0;j<W;++j)
			if(dis(u[i+1][j],u[i][j])<30)
				uni((i+1)*W+j,i*W+j);
	int s0=0; ld s1=0;
	for(int i=0;i<H;++i)
		for(int j=0;j<W;++j) ++cn[gf(i*W+j)];
	for(int i=0;i<H;++i)
		for(int j=0;j<W;++j,++s0)
			if(gf(i*W+j)==i*W+j&&cn[i*W+j]>2) ++s1;
	V10=s1;
	}
	{
	memset(ff,-1,sizeof ff);
	for(int i=0;i<H;++i)
		for(int j=0;j+1<W;++j)
			if(dis(u[i][j],u[i][j+1])<90)
				uni(i*W+j,i*W+j+1);
	for(int i=0;i+1<H;++i)
		for(int j=0;j<W;++j)
			if(dis(u[i+1][j],u[i][j])<90)
				uni((i+1)*W+j,i*W+j);
	int s0=0; ld s1=0;
	for(int i=0;i<H;++i)
		for(int j=0;j<W;++j,++s0)
			if(gf(i*W+j)==i*W+j) ++s1;
	V11=s1/ld(H*W);
	}
	if(V10<25) return 4;
	if(V11>0.003) return 3;
	if(V0>138) return 1;
	return 2;
} //simplify

• Subtask 1: 100 / 100