Submission #762228

#	Time	Username	Problem	Language	Result	Execution time	Memory
762228		SanguineChameleon	Art Class (IOI13_artclass)	C++17	67 / 100	50 ms	3324 KiB

artclass

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

const int BLOCK_CNT = 6;
const int BLOCK_SIZE = (255 / BLOCK_CNT) + 1;
int A[BLOCK_CNT][BLOCK_CNT][BLOCK_CNT];

vector<int> E = {217749,2334,3331,857,0,0,4740,432,574,5601,2777,0,0,0,9,239,5382,598,0,0,0,0,387,41,0,0,0,0,0,0,0,0,0,0,0,0,10595,2652,891,122,0,0,13269,26010,6113,4266,2865,0,76,1167,734,6095,11022,10,0,0,0,26,11987,171,0,0,0,0,1,46,0,0,0,0,0,0,1738,782,168,0,0,0,3652,4601,2184,2936,22432,0,2200,3298,8461,4590,2892,0,0,58,1010,344,1342,102,0,0,0,0,95,157,0,0,0,0,0,0,29825,795,11,0,0,0,1920,2198,267,5,0,0,4201,843,2155,737,47,2,1187,756,7625,21662,10520,37,0,6,81,2697,14927,792,0,0,0,0,0,6,18035,707,0,0,0,0,2380,3103,149,0,0,0,2051,1243,1426,178,0,0,30389,1415,1484,4177,1649,2,85,797,1264,7958,73489,14574,0,0,10,17,6578,23362,17249,520,0,0,0,0,12682,148195,7,0,0,0,441,2276,588,26,0,0,7927,1814,1061,1158,211,0,37583,8294,3438,3274,40058,19288,94011,9101,6894,6363,42837,892169,190966,1290,1,0,0,0,65597,37425,130,0,0,0,40,4873,395,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,60588,1864,1,0,0,0,208528,87177,326,6,0,0,26174,78993,18939,16,0,0,10,131,1199,7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2129,17,0,0,0,0,76406,34178,433,1,0,0,73513,153693,28496,479,26,0,771,12626,15732,3498,92,0,1,4,8,53,1,0,0,0,0,0,0,0,101,0,0,0,0,0,7369,3592,13,0,0,0,34697,73173,9502,247,0,0,7967,56185,51838,35114,3189,30,63,371,1183,10483,3085,1794,0,1,1,4,10,0,1,0,0,0,0,0,81,54,0,0,0,0,1373,5092,574,1,0,0,4397,22289,25971,9028,1846,0,272,2815,10263,57335,60441,8527,20,37,188,318,1242,1449,0,0,0,0,0,0,1,0,0,0,0,0,101,412,6,0,0,0,180,2114,7479,5422,0,0,121,884,1953,14340,5848,460,40,338,458,463,3808,12113,90173,2149,0,0,0,0,3053,1426,2,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30570,1361,1,0,0,0,60381,111836,10963,3,0,0,108,8456,4620,21,0,0,0,0,14,13,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1140,300,0,0,0,0,10206,26591,6083,1,0,0,1912,68711,115371,6198,19,0,0,111,6647,4322,53,0,0,0,0,721,161,0,0,0,0,0,0,0,203,29,0,0,0,0,3315,3226,2678,1,0,0,2501,14826,41862,4191,0,0,185,3836,69495,82677,1626,0,0,1,39,4240,2891,3,0,0,0,0,37,7,173,0,0,0,0,0,1658,291,159,0,0,0,4529,3782,4011,1314,0,0,847,4964,22974,42876,1114,0,35,721,6759,75297,62076,510,0,0,0,9,1353,403,28,0,0,0,0,0,295,84,0,0,0,0,16257,674,47,1,0,0,2492,1781,1632,1109,45,0,1116,3884,7735,22379,28923,238,44,826,4761,17040,113005,61681,44809,2162,0,0,0,0,15793,55424,2567,0,0,0,0,2633,0,78067,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,78573,681,0,0,0,0,475,67161,31942,2283,0,0,0,441,1382,21440,1903,0,0,0,0,33,493,0,0,0,0,0,0,0,0,0,0,0,0,0,106228,2,0,0,0,0,119,448,82,0,0,0,1,965,1881,1308,0,0,0,0,0,65,1,0,0,0,0,0,0,0,0,0,0,0,0,0,65523,3827,0,0,0,0,3844,140,1,0,0,0,499,10502,4466,398,0,0,4185,509,1028,10115,901,0,0,0,0,3,16,0,0,0,0,0,0,0,44194,52,0,0,0,0,9158,20938,35,0,0,0,3255,133950,24013,1,0,0,45619,39858,35976,2116,598,0,7308,6170,2284,4727,8002,18,0,0,0,4,43,217,106288,446,0,0,0,0,109431,187,0,0,0,0,8862,88,20,129,0,0,20887,13701,367,169,482,0,69099,34564,2956,3225,1369,83,523,706,3119,18012,31888,32544,};

int style(int N, int M, int R[500][500], int G[500][500], int B[500][500]) {
	for (int r = 0; r < BLOCK_CNT; r++) {
		for (int g = 0; g < BLOCK_CNT; g++) {
			for (int b = 0; b < BLOCK_CNT; b++) {
				A[r][g][b] = 1;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			A[R[i][j] / BLOCK_SIZE][G[i][j] / BLOCK_SIZE][B[i][j] / BLOCK_SIZE]++;
		}
	}
	pair<long double, int> res = make_pair(1e18L, -1);
	for (int X = 0; X < 4; X++) {
		long double score = 0.0L;
		int totA = 0;
		int totE = 0;
		for (int r = 0; r < BLOCK_CNT; r++) {
			for (int g = 0; g < BLOCK_CNT; g++) {
				for (int b = 0; b < BLOCK_CNT; b++) {
					totA += A[r][g][b];
					totE += E[X * BLOCK_CNT * BLOCK_CNT * BLOCK_CNT + r * BLOCK_CNT * BLOCK_CNT + g * BLOCK_CNT + b] + 1;
				}
			}
		}
		for (int r = 0; r < BLOCK_CNT; r++) {
			for (int g = 0; g < BLOCK_CNT; g++) {
				for (int b = 0; b < BLOCK_CNT; b++) {
					long double exp = 1.0L * (E[X * BLOCK_CNT * BLOCK_CNT * BLOCK_CNT + r * BLOCK_CNT * BLOCK_CNT + g * BLOCK_CNT + b] + 1) / totE * totA;
					score += (exp - A[r][g][b]) * (exp - A[r][g][b]) / exp;
				}
			}
		}
		res = min(res, make_pair(score, X + 1));
	}
	return res.second;
}

• Subtask 1: 67 / 100