Submission #762204

#	Time	Username	Problem	Language	Result	Execution time	Memory
762204		SanguineChameleon	Art Class (IOI13_artclass)	C++17	29 / 100	56 ms	3292 KiB

artclass

#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;

const int BLOCK_CNT = 32;
const int BLOCK_SIZE = 256 / BLOCK_CNT;
int A[BLOCK_CNT][3];
int E[4][BLOCK_CNT][3];

int style(int N, int M, int R[500][500], int G[500][500], int B[500][500]) {
	E[0][0][0] = 74449;
	E[0][0][1] = 114158;
	E[0][0][2] = 271205;
	E[0][1][0] = 43364;
	E[0][1][1] = 55514;
	E[0][1][2] = 89618;
	E[0][2][0] = 40930;
	E[0][2][1] = 47443;
	E[0][2][2] = 66802;
	E[0][3][0] = 50378;
	E[0][3][1] = 58693;
	E[0][3][2] = 46095;
	E[0][4][0] = 28834;
	E[0][4][1] = 25463;
	E[0][4][2] = 30313;
	E[0][5][0] = 17656;
	E[0][5][1] = 18072;
	E[0][5][2] = 26567;
	E[0][6][0] = 18009;
	E[0][6][1] = 20254;
	E[0][6][2] = 64452;
	E[0][7][0] = 19110;
	E[0][7][1] = 35666;
	E[0][7][2] = 74118;
	E[0][8][0] = 19546;
	E[0][8][1] = 88259;
	E[0][8][2] = 46163;
	E[0][9][0] = 19291;
	E[0][9][1] = 95426;
	E[0][9][2] = 15143;
	E[0][10][0] = 15798;
	E[0][10][1] = 28284;
	E[0][10][2] = 9147;
	E[0][11][0] = 21848;
	E[0][11][1] = 20128;
	E[0][11][2] = 8617;
	E[0][12][0] = 17886;
	E[0][12][1] = 13706;
	E[0][12][2] = 8723;
	E[0][13][0] = 7878;
	E[0][13][1] = 8299;
	E[0][13][2] = 8769;
	E[0][14][0] = 5450;
	E[0][14][1] = 6596;
	E[0][14][2] = 9552;
	E[0][15][0] = 5088;
	E[0][15][1] = 7579;
	E[0][15][2] = 10770;
	E[0][16][0] = 5634;
	E[0][16][1] = 12293;
	E[0][16][2] = 10196;
	E[0][17][0] = 7501;
	E[0][17][1] = 17722;
	E[0][17][2] = 11028;
	E[0][18][0] = 17325;
	E[0][18][1] = 17968;
	E[0][18][2] = 11752;
	E[0][19][0] = 33672;
	E[0][19][1] = 19529;
	E[0][19][2] = 14624;
	E[0][20][0] = 25926;
	E[0][20][1] = 26584;
	E[0][20][2] = 16488;
	E[0][21][0] = 29453;
	E[0][21][1] = 32404;
	E[0][21][2] = 23921;
	E[0][22][0] = 32326;
	E[0][22][1] = 33137;
	E[0][22][2] = 39973;
	E[0][23][0] = 36669;
	E[0][23][1] = 35258;
	E[0][23][2] = 49649;
	E[0][24][0] = 29525;
	E[0][24][1] = 34266;
	E[0][24][2] = 44497;
	E[0][25][0] = 32627;
	E[0][25][1] = 44269;
	E[0][25][2] = 49738;
	E[0][26][0] = 59819;
	E[0][26][1] = 78944;
	E[0][26][2] = 63764;
	E[0][27][0] = 111740;
	E[0][27][1] = 175260;
	E[0][27][2] = 122463;
	E[0][28][0] = 214477;
	E[0][28][1] = 236816;
	E[0][28][2] = 244653;
	E[0][29][0] = 343476;
	E[0][29][1] = 216960;
	E[0][29][2] = 271342;
	E[0][30][0] = 288978;
	E[0][30][1] = 287586;
	E[0][30][2] = 178660;
	E[0][31][0] = 388837;
	E[0][31][1] = 150964;
	E[0][31][2] = 124698;
	E[1][0][0] = 28254;
	E[1][0][1] = 24492;
	E[1][0][2] = 50007;
	E[1][1][0] = 54195;
	E[1][1][1] = 30097;
	E[1][1][2] = 99460;
	E[1][2][0] = 55425;
	E[1][2][1] = 49413;
	E[1][2][2] = 156230;
	E[1][3][0] = 62123;
	E[1][3][1] = 63518;
	E[1][3][2] = 184224;
	E[1][4][0] = 71542;
	E[1][4][1] = 64416;
	E[1][4][2] = 199381;
	E[1][5][0] = 80697;
	E[1][5][1] = 69422;
	E[1][5][2] = 182453;
	E[1][6][0] = 89277;
	E[1][6][1] = 78968;
	E[1][6][2] = 146756;
	E[1][7][0] = 93135;
	E[1][7][1] = 92384;
	E[1][7][2] = 115270;
	E[1][8][0] = 92362;
	E[1][8][1] = 105258;
	E[1][8][2] = 90943;
	E[1][9][0] = 91044;
	E[1][9][1] = 113672;
	E[1][9][2] = 72059;
	E[1][10][0] = 88595;
	E[1][10][1] = 115083;
	E[1][10][2] = 57686;
	E[1][11][0] = 83215;
	E[1][11][1] = 112260;
	E[1][11][2] = 45488;
	E[1][12][0] = 78019;
	E[1][12][1] = 107110;
	E[1][12][2] = 35597;
	E[1][13][0] = 73994;
	E[1][13][1] = 96321;
	E[1][13][2] = 28571;
	E[1][14][0] = 69610;
	E[1][14][1] = 84589;
	E[1][14][2] = 24849;
	E[1][15][0] = 67069;
	E[1][15][1] = 73525;
	E[1][15][2] = 24279;
	E[1][16][0] = 64354;
	E[1][16][1] = 64344;
	E[1][16][2] = 24913;
	E[1][17][0] = 60817;
	E[1][17][1] = 55335;
	E[1][17][2] = 25777;
	E[1][18][0] = 57656;
	E[1][18][1] = 48246;
	E[1][18][2] = 25955;
	E[1][19][0] = 53624;
	E[1][19][1] = 43132;
	E[1][19][2] = 27253;
	E[1][20][0] = 49562;
	E[1][20][1] = 41837;
	E[1][20][2] = 24190;
	E[1][21][0] = 43361;
	E[1][21][1] = 48260;
	E[1][21][2] = 23928;
	E[1][22][0] = 41166;
	E[1][22][1] = 56576;
	E[1][22][2] = 23136;
	E[1][23][0] = 42909;
	E[1][23][1] = 41479;
	E[1][23][2] = 14888;
	E[1][24][0] = 42004;
	E[1][24][1] = 26355;
	E[1][24][2] = 9229;
	E[1][25][0] = 39078;
	E[1][25][1] = 18659;
	E[1][25][2] = 8884;
	E[1][26][0] = 30332;
	E[1][26][1] = 13395;
	E[1][26][2] = 13117;
	E[1][27][0] = 17132;
	E[1][27][1] = 11763;
	E[1][27][2] = 15209;
	E[1][28][0] = 8822;
	E[1][28][1] = 5607;
	E[1][28][2] = 6722;
	E[1][29][0] = 5587;
	E[1][29][1] = 1060;
	E[1][29][2] = 536;
	E[1][30][0] = 4912;
	E[1][30][1] = 267;
	E[1][30][2] = 8;
	E[1][31][0] = 17128;
	E[1][31][1] = 157;
	E[1][31][2] = 2;
	E[2][0][0] = 6008;
	E[2][0][1] = 10417;
	E[2][0][2] = 60667;
	E[2][1][0] = 11062;
	E[2][1][1] = 15252;
	E[2][1][2] = 39132;
	E[2][2][0] = 15091;
	E[2][2][1] = 22157;
	E[2][2][2] = 37743;
	E[2][3][0] = 20264;
	E[2][3][1] = 29553;
	E[2][3][2] = 37446;
	E[2][4][0] = 30565;
	E[2][4][1] = 34831;
	E[2][4][2] = 40374;
	E[2][5][0] = 38210;
	E[2][5][1] = 38338;
	E[2][5][2] = 42992;
	E[2][6][0] = 40638;
	E[2][6][1] = 40989;
	E[2][6][2] = 44991;
	E[2][7][0] = 41336;
	E[2][7][1] = 43141;
	E[2][7][2] = 46922;
	E[2][8][0] = 42770;
	E[2][8][1] = 45525;
	E[2][8][2] = 49462;
	E[2][9][0] = 44566;
	E[2][9][1] = 49131;
	E[2][9][2] = 51498;
	E[2][10][0] = 46193;
	E[2][10][1] = 52216;
	E[2][10][2] = 53320;
	E[2][11][0] = 46488;
	E[2][11][1] = 54848;
	E[2][11][2] = 55267;
	E[2][12][0] = 46069;
	E[2][12][1] = 56189;
	E[2][12][2] = 57146;
	E[2][13][0] = 45924;
	E[2][13][1] = 58717;
	E[2][13][2] = 57996;
	E[2][14][0] = 46329;
	E[2][14][1] = 56813;
	E[2][14][2] = 57930;
	E[2][15][0] = 46433;
	E[2][15][1] = 53318;
	E[2][15][2] = 57038;
	E[2][16][0] = 45823;
	E[2][16][1] = 50087;
	E[2][16][2] = 54722;
	E[2][17][0] = 44960;
	E[2][17][1] = 48355;
	E[2][17][2] = 51816;
	E[2][18][0] = 43938;
	E[2][18][1] = 46896;
	E[2][18][2] = 49522;
	E[2][19][0] = 43547;
	E[2][19][1] = 45000;
	E[2][19][2] = 46822;
	E[2][20][0] = 43642;
	E[2][20][1] = 43678;
	E[2][20][2] = 44616;
	E[2][21][0] = 43542;
	E[2][21][1] = 42531;
	E[2][21][2] = 43126;
	E[2][22][0] = 43977;
	E[2][22][1] = 42697;
	E[2][22][2] = 40687;
	E[2][23][0] = 44478;
	E[2][23][1] = 41948;
	E[2][23][2] = 38622;
	E[2][24][0] = 43787;
	E[2][24][1] = 40098;
	E[2][24][2] = 38447;
	E[2][25][0] = 43555;
	E[2][25][1] = 38412;
	E[2][25][2] = 39505;
	E[2][26][0] = 43648;
	E[2][26][1] = 37966;
	E[2][26][2] = 36984;
	E[2][27][0] = 43778;
	E[2][27][1] = 37932;
	E[2][27][2] = 24710;
	E[2][28][0] = 45234;
	E[2][28][1] = 40187;
	E[2][28][2] = 16955;
	E[2][29][0] = 50233;
	E[2][29][1] = 46502;
	E[2][29][2] = 9663;
	E[2][30][0] = 56893;
	E[2][30][1] = 49419;
	E[2][30][2] = 5031;
	E[2][31][0] = 84519;
	E[2][31][1] = 20357;
	E[2][31][2] = 2348;
	E[3][0][0] = 6656;
	E[3][0][1] = 107616;
	E[3][0][2] = 261596;
	E[3][1][0] = 8531;
	E[3][1][1] = 17082;
	E[3][1][2] = 161437;
	E[3][2][0] = 43444;
	E[3][2][1] = 85739;
	E[3][2][2] = 116308;
	E[3][3][0] = 56843;
	E[3][3][1] = 151365;
	E[3][3][2] = 123634;
	E[3][4][0] = 69781;
	E[3][4][1] = 71226;
	E[3][4][2] = 58738;
	E[3][5][0] = 49525;
	E[3][5][1] = 50532;
	E[3][5][2] = 57180;
	E[3][6][0] = 60769;
	E[3][6][1] = 66482;
	E[3][6][2] = 99036;
	E[3][7][0] = 42204;
	E[3][7][1] = 71059;
	E[3][7][2] = 99218;
	E[3][8][0] = 25382;
	E[3][8][1] = 56550;
	E[3][8][2] = 85941;
	E[3][9][0] = 24826;
	E[3][9][1] = 66462;
	E[3][9][2] = 49008;
	E[3][10][0] = 26969;
	E[3][10][1] = 34997;
	E[3][10][2] = 37309;
	E[3][11][0] = 36934;
	E[3][11][1] = 26077;
	E[3][11][2] = 32062;
	E[3][12][0] = 44072;
	E[3][12][1] = 96126;
	E[3][12][2] = 24254;
	E[3][13][0] = 18257;
	E[3][13][1] = 63770;
	E[3][13][2] = 16851;
	E[3][14][0] = 3536;
	E[3][14][1] = 40606;
	E[3][14][2] = 14947;
	E[3][15][0] = 1474;
	E[3][15][1] = 54175;
	E[3][15][2] = 13226;
	E[3][16][0] = 1422;
	E[3][16][1] = 40128;
	E[3][16][2] = 9786;
	E[3][17][0] = 1796;
	E[3][17][1] = 27310;
	E[3][17][2] = 12275;
	E[3][18][0] = 3571;
	E[3][18][1] = 32224;
	E[3][18][2] = 40968;
	E[3][19][0] = 11752;
	E[3][19][1] = 32730;
	E[3][19][2] = 59573;
	E[3][20][0] = 48550;
	E[3][20][1] = 36922;
	E[3][20][2] = 15418;
	E[3][21][0] = 70209;
	E[3][21][1] = 30559;
	E[3][21][2] = 11387;
	E[3][22][0] = 72870;
	E[3][22][1] = 41712;
	E[3][22][2] = 8487;
	E[3][23][0] = 67964;
	E[3][23][1] = 47670;
	E[3][23][2] = 7145;
	E[3][24][0] = 100495;
	E[3][24][1] = 25890;
	E[3][24][2] = 8511;
	E[3][25][0] = 40674;
	E[3][25][1] = 8565;
	E[3][25][2] = 8944;
	E[3][26][0] = 90081;
	E[3][26][1] = 2653;
	E[3][26][2] = 8584;
	E[3][27][0] = 126626;
	E[3][27][1] = 2863;
	E[3][27][2] = 6505;
	E[3][28][0] = 133305;
	E[3][28][1] = 4234;
	E[3][28][2] = 4899;
	E[3][29][0] = 55491;
	E[3][29][1] = 5323;
	E[3][29][2] = 5723;
	E[3][30][0] = 29421;
	E[3][30][1] = 7331;
	E[3][30][2] = 8441;
	E[3][31][0] = 99570;
	E[3][31][1] = 67022;
	E[3][31][2] = 5609;
	for (int i = 0; i < BLOCK_CNT; i++) {
		for (int j = 0; j < 3; j++) {
			A[i][j] = 0;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			A[R[i][j] / BLOCK_SIZE][0]++;
			A[G[i][j] / BLOCK_SIZE][1]++;
			A[B[i][j] / BLOCK_SIZE][2]++;
		}
	}
	pair<long double, int> res = make_pair(1e18L, -1);
	for (int X = 0; X < 4; X++) {
		long double score = 0.0L;
		for (int i = 0; i < 3; i++) {
			int totA = 0;
			int totE = 0;
			for (int j = 0; j < BLOCK_CNT; j++) {
				totA += A[j][i];
				totE += E[X][j][i];
			}
			for (int j = 0; j < BLOCK_CNT; j++) {
				long double exp = 1.0L * E[X][j][i] / totE * totA;
				score += (exp - A[j][i]) * (exp - A[j][i]) / exp; 
			}
		}
		res = min(res, make_pair(score, X + 1));
	}
	return res.second;
}

• Subtask 1: 29 / 100