Submission #280558

#	Time	Username	Problem	Language	Result	Execution time	Memory
280558		amoo_safar	Art Class (IOI13_artclass)	C++17	100 / 100	103 ms	21648 KiB

artclass

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

#define F first
#define S second

using namespace std;

typedef pair<int, int> pii;
const int N = 510;

int H, W;
int R[N][N], G[N][N], B[N][N];
int mk[N][N];

const int Tr = 70;
bool Same(int X1, int Y1, int X2, int Y2){
	return abs(R[X1][Y1] - R[X2][Y2]) + abs(G[X1][Y1] - G[X2][Y2]) + abs(B[X1][Y1] - B[X2][Y2]) <= Tr;
}
bool VerySame(int X1, int Y1, int X2, int Y2){
	return abs(R[X1][Y1] - R[X2][Y2]) + abs(G[X1][Y1] - G[X2][Y2]) + abs(B[X1][Y1] - B[X2][Y2]) <= Tr/2;
}

const int Tr2 = 70;
bool Diff(int X1, int Y1, int X2, int Y2){
	return abs(R[X1][Y1] - R[X2][Y2]) + abs(G[X1][Y1] - G[X2][Y2]) + abs(B[X1][Y1] - B[X2][Y2]) >= Tr2;
}

bool Valid(int X1, int Y1){
	return (0 <= X1) && (X1 < H) && (0 <= Y1) && (Y1 < W);
}
bool Yellow(int X1, int Y1){
	return (60 <= R[X1][Y1]) && (R[X1][Y1] <= 150) && (G[X1][Y1] <= 30) && (B[X1][Y1] <= 30);
}
bool Green(int X1, int Y1){
	return (75 <= G[X1][Y1]) && (R[X1][Y1] <= 40) && (B[X1][Y1] <= 40);	
}


pii del[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void DFS(int X, int Y, int c){
	//cerr << "# " << X << ' ' << Y << '\n'; 
	mk[X][Y] = c;
	int nx, ny;
	int dx, dy;
	for(auto vec : del){
		dx = vec.F; dy = vec.S;
		nx = X + dx; ny = Y + dy;
		if(!Valid(nx, ny)) continue;
		if(mk[nx][ny]) continue;
		if(Same(X, Y, nx, ny))
			DFS(nx, ny, c);
	}
}

int style(int _H, int _W, int _R[500][500], int _G[500][500], int _B[500][500]){
	//return 4;

	H = _H; W = _W;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			R[i][j] = _R[i][j];
			G[i][j] = _G[i][j];
			B[i][j] = _B[i][j];
		}
	}
	//cerr << H << ' ' << W << '\n';
	int cnt = 0;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(mk[i][j]) continue;
			//cerr << i << ' ' << j << '\n';
			cnt ++;
			DFS(i, j, cnt);
		}
	}
	//cerr << H << ", " << W << ' ' << cnt << '\n';
	if(cnt < 25) return 4;
	// 22 AC 1 WA


	int cntdiff = 0;
	int nx, ny;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			for(auto vec : del){
				nx = i + vec.F;
				ny = j + vec.S;
				if(Valid(nx, ny) && Diff(i, j, nx, ny)) cntdiff ++;
			}
		}
	}
	double K = 0.85;
	if(H*W / K <= cntdiff) return 3;
	// 25 AC 1 WA

	int cntgd = 0;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			bool flg = true;
			for(auto vec : del){
				nx = i + vec.F;
				ny = j + vec.S;
				if(Valid(nx, ny) && !VerySame(i, j, nx, ny)) flg = false;
			}
			if(flg) cntgd ++;
		}
	}


	K = 0.63;
	if(H*W * K <= cntgd) return 1;
	return 2;

	assert(false);

	int cntYG = 0;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(Yellow(i, j)) cntYG ++;
			if(Green(i, j)) cntYG ++;
		}
	}
	K = 0.85;
	if(H*W * K <= cntdiff) return 2;

	assert(false);
	if(cnt < 20) return 1;
	if(cnt > 60) return 3;
	return 2;
	assert(false);
}

• Subtask 1: 100 / 100