제출 #17187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17187		erdemkiraz	미술 수업 (IOI13_artclass)	C++98	100 / 100	460 ms	21240 KiB

artclass

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

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 500;

int n, m, r[N][N], g[N][N], b[N][N];
ii root[N][N];

ii f(int x, int y) {
	if(root[x][y] == ii(0, 0) or root[x][y] == ii(x, y))
		return ii(x, y);
	return root[x][y] = f(root[x][y].first, root[x][y].second);
}

void road(int x1, int y1, int x2, int y2, int A, int B, int C, int x = 0) {
	bool flag = 0;
	if(x2 < n and y2 < m) {
		flag = 1;
		flag &= abs(r[x1][y1] - r[x2][y2]) <= A;
		flag &= abs(g[x1][y1] - g[x2][y2]) <= B;
		flag &= abs(b[x1][y1] - b[x2][y2]) <= C;
		if(x) {
			flag &= g[x1][y1] >= r[x2][y2] - x;
			flag &= g[x1][y1] >= b[x2][y2] - x;
		}
	}
	if(flag) {
		int X1 = f(x1, y1).first;
		int Y1 = f(x1, y1).second;
		int X2 = f(x2, y2).first;
		int Y2 = f(x2, y2).second;
		root[X1][Y1] = ii(X2, Y2);
	}
}

bool h[N][N];

int style(int n, int m, int R[500][500], int G[500][500], int B[500][500]) {
	:: n = n;
	:: m = m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			r[i][j] = R[i][j];
			g[i][j] = G[i][j];
			b[i][j] = B[i][j];
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			road(i, j, i, j + 1, 20, 20, 20);
			road(i, j, i + 1, j, 20, 20, 20);
		}
	}
	set < ii > cntr;
	multiset < ii > cntrMul;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cntr.insert(f(i, j));
			cntrMul.insert(f(i, j));
		}
	}
	//printf("cntr.size() %d\n", (int) cntr.size());
	if(cntr.size() <= 50)
		return 4;
	int bigs = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int x = f(i, j).first;
			int y = f(i, j).second;
			if(!h[x][y]) {
				h[x][y] = 1;
				if(cntrMul.count(ii(x, y)) >= 1000) {
					bigs++;
				}
			}
		}
	}
	if(bigs < 4 and cntr.size() <= 100)
		return 4;
	//printf("n = %d m = %d\n", n, m);
	//printf("bigs = %d\n", bigs);
	//printf("cntr = %d\n", (int) cntr.size());
	if(cntr.size() <= 5000 and bigs >= 5)
		return 1;
	if(bigs > 2 and bigs * 1200 >= cntr.size())
		return 1;

	cntr.clear();
	cntrMul.clear();
	memset(root, 0, sizeof(root));

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			road(i, j, i, j + 1, 20, 50, 50, 0);
			road(i, j, i + 1, j, 20, 50, 50, 0);
		}
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cntr.insert(f(i, j));
			cntrMul.insert(f(i, j));
		}
	}

	memset(h, 0, sizeof(h));

	bigs = 0;

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int x = f(i, j).first;
			int y = f(i, j).second;
			if(!h[x][y]) {
				h[x][y] = 1;
				if(cntrMul.count(ii(x, y)) >= 600) {
					bigs++;
				}
			}
		}
	}

	//printf("bigs = %d\n", bigs);
	//printf("%d\n", (int) cntr.size());

	if(cntr.size() <= 15000)
		return 2;

	if(cntr.size() <= 17000 and bigs >= 4)
		return 2;

	return 3;
}

컴파일 시 표준 에러 (stderr) 메시지

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:95:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(bigs > 2 and bigs * 1200 >= cntr.size())
                  ~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100