Submission #222888

#	Time	Username	Problem	Language	Result	Execution time	Memory
222888		staniewzki	Art Class (IOI13_artclass)	C++17	100 / 100	99 ms	28024 KiB

artclass

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

#include "artclass.h"

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
	int res = 0;
	auto dst = [&](int a, int b, int c, int d) {
		int delta_R = R[a][b] - R[c][d];
		int delta_G = G[a][b] - G[c][d];
		int delta_B = B[a][b] - B[c][d];

		delta_R *= delta_R;
		delta_G *= delta_G;
		delta_B *= delta_B;
		bool ret = delta_R + delta_G + delta_B <= 2000;
		res += ret;
		return ret;
	};

	array dx = {0, 0, +1, -1};
	array dy = {+1, -1, 0, 0};
	auto valid = [&](int x, int y) {
		return 0 <= x && x < H && 0 <= y && y < W;
	};

	vector<vector<bool>> vis(H, vector<bool>(W));
	function<void(int, int)> dfs = [&](int x, int y) {
		vis[x][y] = true;
		REP(dir, 4) {
			int _x = x + dx[dir];
			int _y = y + dy[dir];
			if(not valid(_x, _y)) continue;
			if(not vis[_x][_y] && dst(x, y, _x, _y))
				dfs(_x, _y);
		}
	};

	int components = 0;
	REP(i, H) REP(j, W) if(not vis[i][j]) {
		components++;
		dfs(i, j);
	}

	int white = 0;
	REP(i, H) REP(j, W) {
		if(R[i][j] >= 230 && G[i][j] >= 230 && B[i][j] >= 230)
			white++;
	}

	int sum_R = 0, sum_G = 0, sum_B = 0;
	REP(i, H) REP(j, W) {
		sum_R += R[i][j];
		sum_G += G[i][j];
		sum_B += B[i][j];
	}

	sum_R /= (H * W);
	sum_G /= (H * W);
	sum_B /= (H * W);
	res = res * 100 / (H * W);

	int scaled_comps = components * 1000 / (H * W);
	debug(components, white, min({sum_R, sum_G, sum_B}), res, scaled_comps);

	if(components <= 15) return 4;
	if(res > 95 && min({sum_R, sum_G, sum_B}) < 90) return 2;
	if(scaled_comps <= 50) return 1;
	return 3;

	return -1;
}

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:102:73: warning: statement has no effect [-Wunused-value]
  debug(components, white, min({sum_R, sum_G, sum_B}), res, scaled_comps);
                                                                         ^

• Subtask 1: 100 / 100