Submission #586644

#	Time	Username	Problem	Language	Result	Execution time	Memory
586644		AlperenT	Art Class (IOI13_artclass)	C++17	69 / 100	102 ms	9236 KiB

artclass

#include <bits/stdc++.h>
#include "artclass.h"

using namespace std;

const int N = 500;
const int ISSAME_THRESHOLD = 35;
const int ISGREEN_THRESHOLD = 35;
const bool IS_MAX = true;

const int GREEN = 31;
const int CNTMIN = 11;
const int CNTMAX = 800;

const int K = 8;
const int xd[K] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int yd[K] = {0, 1, 1, 1, 0, -1, -1, -1};

int h, w, greencnt;

array<int, 3> color[N][N];

struct DSU{
	pair<int, int> par[N][N];
	int setsize[N][N];

	int setcnt;

	void reset(int n, int m){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				par[i][j] = {i, j};
				setsize[i][j] = 1;
			}
		}

		setcnt = n * m;
	}

	pair<int, int> setfind(pair<int, int> a){
		if(par[a.first][a.second] == a) return a;
		else return par[a.first][a.second] = setfind(par[a.first][a.second]);
	}

	void setunion(pair<int, int> a, pair<int, int> b){
		a = setfind(a), b = setfind(b);

		if(a != b){
			if(setsize[b.first][b.second] > setsize[a.first][a.second]) swap(a, b);

			par[b.first][b.second] = a;
			setsize[a.first][a.second] += setsize[b.first][b.second];

			setcnt--;
		}
	}
};

DSU dsu;

bool issame(array<int, 3> a, array<int, 3> b){
	int diff;

	if(IS_MAX) diff = max({abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2])});
	else diff = abs(a[0] - b[0]) + abs(a[1] - b[1]) + abs(a[2] - b[2]);

	return diff <= ISSAME_THRESHOLD;
}

bool isgreen(array<int, 3> a){
	// return (a[1] - max(a[0], a[2])) >= ISGREEN_THRESHOLD;

	// return ((a[1] - a[2] >= ISGREEN_THRESHOLD) || (a[2] - a[1] <= ISGREEN_THRESHOLD / 20)) && ((a[1] - a[0] >= ISGREEN_THRESHOLD) || (a[0] - a[1] <= ISGREEN_THRESHOLD));

	return (a[1] - a[2]) >= ISGREEN_THRESHOLD / 1.2 && ((a[1] - a[0] >= ISGREEN_THRESHOLD) || (a[0] - a[1] <= ISGREEN_THRESHOLD));
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]){
	h = H, w = W;

	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			color[i][j] = {R[i][j], G[i][j], B[i][j]};
		}
	}

	dsu.reset(h, w);

	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			for(int k = 0; k < K; k++){
				int x = i + xd[k], y = j + yd[k];

				if(x >= 0 && x < h && y >= 0 && y < w && issame(color[i][j], color[x][y])){
					dsu.setunion({i, j}, {x, y});
				}
			}

			greencnt += isgreen(color[i][j]);
		}
	}

	if(greencnt * 100 / (h * w) >= GREEN) return 2;
	else if(dsu.setcnt <= CNTMIN) return 4;
	else if(dsu.setcnt <= CNTMAX) return 1;
	else return 3;

    return -1;
}

• Subtask 1: 69 / 100