Submission #425315

#	Time	Username	Problem	Language	Result	Execution time	Memory
425315		frodakcin	Art Class (IOI13_artclass)	C++17	34 / 100	3874 ms	8156 KiB

artclass

#include "artclass.h"
#include <random>
#include <chrono>
#include <vector>
#include <algorithm>

std::mt19937 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
	auto dist=[&](int a, int b, int x, int y)->double
	{
		double d2=0;
		d2 += (R[a][b]-R[x][y])*(R[a][b]-R[x][y]);
		d2 += (G[a][b]-G[x][y])*(G[a][b]-G[x][y]);
		d2 += (B[a][b]-B[x][y])*(B[a][b]-B[x][y]);
		return sqrt(d2);
	};

	auto logistic=[&](double x)->double
	{
		const double x0 = 0;
		const double rt = 0.2;
		return 1/(1+exp((x-x0)*rt));
	};

	// differentiate between 1/4 and 2/3
	double wtdif = 0;
	for(int i=0;i+1<H;++i)
		for(int j=0;j<W;++j)
			wtdif += logistic(dist(i, j, i+1, j));
	wtdif /= (H-1)*W;

	// return (int)(wtdif*10000); // CUT: 1800

	if(wtdif < 0.18)
	{ // styles 2 or 3
		/*
		double green_factor = 0;
		for(int i=0;i<H;++i)
			for(int j=0;j<W;++j)
				green_factor += (double)G[i][j]/(R[i][j]+G[i][j]+B[i][j]+1);
		green_factor /= H*W;
		*/

		std::vector<double> vars;

		int L = ((H+W)/2)/20;
		for(int i=L;i+L<=H;++i)
			for(int j=L;j+L<=W;++j)
			{
				auto var_col = [&](int col[500][500])->double
				{
					double mean = 0;
					for(int u=i-L;u<i+L;++u)
						for(int v=j-L;v<j+L;++v)
							mean += col[u][v];
					mean /= L*L*4;

					double var = 0;
					for(int u=i-L;u<i+L;++u)
						for(int v=j-L;v<j+L;++v)
							var += (col[u][v]-mean)*(col[u][v]-mean);
					var /= L*L*4;
					return var;
				};

				double var_cur=0;
				var_cur += var_col(R);
				var_cur += var_col(G);
				var_cur += var_col(B);
				vars.push_back(var_cur);
			}
		std::sort(vars.begin(), vars.end());

		
		//return (int)(vars[vars.size()/4]);
		//return (int)(green_factor*1000);

		if(vars[vars.size()/4] < 3200)
			return 2;
		else
			return 3;
	}
	else
	{ // styles 1 or 4
		double variance = 0;

		auto var_col = [&](int col[500][500])->double
		{
			double mean = 0;
			for(int u=0;u<H;++u)
				for(int v=0;v<W;++v)
					mean += col[u][v];
			mean /= H*W;

			double var = 0;
			for(int u=0;u<H;++u)
				for(int v=0;v<W;++v)
					var += (col[u][v]-mean)*(col[u][v]-mean);
			var /= H*W;
			return var;
		};

		variance += var_col(R);
		variance += var_col(G);
		variance += var_col(B);
		
		if(variance < 10000)
			return 1;
		else
			return 4;
	}
	return -1;
}

• Subtask 1: 34 / 100