Submission #399142

#	Time	Username	Problem	Language	Result	Execution time	Memory
399142		prvocislo	Art Class (IOI13_artclass)	C++17	80 / 100	85 ms	7224 KiB

artclass

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <queue>
#include "artclass.h"
typedef long long ll;
using namespace std;

const int dx[4] = { 1, 1, -1, -1 }, dy[4] = { -1, 1, -1, 1 }, maxn = 500;
int h, w;
bool valid(int x, int y) { return 0 <= x && x < h && 0 <= y && y < w; }
vector<vector<int> > vis, r(maxn, vector<int>(maxn)), g(maxn, vector<int>(maxn)), b(maxn, vector<int>(maxn));
bool black(int x, int y) { return r[x][y] + b[x][y] + g[x][y] < 100; }
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]) < 75;
}
bool green(int x, int y)
{
	return b[x][y] < g[x][y] && r[x][y] < g[x][y];
}
int style(int H, int W, int R[500][500], int G[500][500], int B[500][500])
{
	h = H, w = W; vis.assign(h, vector<int>(w, 0));
	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];
	int big = 0, small = 0, semi = 0, gr = 0;
	int minx = h, miny = w, maxx = 0, maxy = 0;
	for (int i = 0; i < h; i++) for (int j = 0; j < w; j++)
	{
		gr += 2 * g[i][j] - r[i][j] - b[i][j];
		if (black(i, j))
		{
			minx = min(i, minx), maxx = max(i, maxx);
			miny = min(j, miny), maxy = max(j, maxy);
		}
		if (!vis[i][j])
		{
			int siz = 0;
			queue<pair<int, int> > q; q.push({ i, j });
			while (!q.empty())
			{
				int x, y;
				tie(x, y) = q.front(); q.pop(); siz++;
				for (int i = 0; i < 4; i++)
				{
					int xi = x + dx[i], yi = y + dy[i];
					if (!valid(xi, yi) || !same(x, y, xi, yi) || vis[xi][yi]) continue;
					q.push({ xi, yi }); vis[xi][yi] = true;
				}
			}
			if (siz > (h * w) / 50) semi++;
			if (siz > (h * w) / 20) big++;
			else small++;
		}
	}
	//cout << h * w << " " << big << " " << semi << " " << small << " " << gr << "\n";
	int mx = abs(minx - maxx), my = abs(miny - maxy); // pre styl 1 mame vela nahodnej ciernej
	if (small >= (h * w) / 10) return 3;
	if (10 <= semi && mx >= (h / 8) * 7 && my >= (w / 8) * 7) return 1;
	if (gr > (H * W)) return 2;
	if (big) return 4;
	return 3;
}

• Subtask 1: 80 / 100