Submission #41051

#	Time	Username	Problem	Language	Result	Execution time	Memory
41051		tkqlzz	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	45 / 100	2 ms	620 KiB

treasure

#include "treasure.h"
#define MAX(A, B) ((A) > (B) ? (A) : (B))

int map[101][101];


void _fill(int y, int x, int h, int w) {
	for (int i = y; i <= y + h - 1; i++)
		for (int j = x; j <= x + w - 1; j++)
			map[i][j] = 1;
}

int dfs(int y, int x, int h, int w) {
	int cnt = countTreasure(y, x, y+h-1, x+w-1);
	if (cnt == 0)
		return cnt;
	if (cnt == h*w) {
		_fill(y, x, h, w);
		return cnt;
	}
	
	int ys[4], xs[4], hs[4], ws[4], areas[4];
	ys[0] = y;
	ys[1] = y;
	ys[2] = y + h / 2;
	ys[3] = y + h / 2;
	xs[0] = x;
	xs[1] = x + w / 2;
	xs[2] = x;
	xs[3] = x + w / 2;
	hs[0] = MAX(1, h / 2);
	hs[1] = MAX(1, h / 2);
	hs[2] = MAX(1, h / 2 + (h & 1 ? 1 : 0));
	hs[3] = MAX(1, h / 2 + (h & 1 ? 1 : 0));
	ws[0] = MAX(1, w / 2);
	ws[1] = MAX(1, w / 2 + (w & 1 ? 1 : 0));
	ws[2] = MAX(1, w / 2);
	ws[3] = MAX(1, w / 2 + (w & 1 ? 1 : 0));
	areas[0] = h*w - hs[0] * ws[0];
	areas[1] = areas[0] - hs[1] * ws[1];
	areas[2] = areas[1] - hs[2] * ws[2];
	areas[3] = areas[2] - hs[3] * ws[3];

	int s = 0, t;
	for (int i = 0; i < 4; i++) {
		if (h == 1 && i >= 2)
			continue;
		if (w == 1 && (i == 1 || i == 3))
			continue;

		t = dfs(ys[i], xs[i], hs[i], ws[i]);
		s += t;
		if (s == cnt)
			return cnt;
		if (cnt-s == areas[i] && areas[i] != 0) {
			for (int j = i+1; j < 4; j++) {
				if (h == 1 && j >= 2)
					continue;
				if (w == 1 && (j == 1 || j == 3))
					continue;
				_fill(ys[j], xs[j], hs[j], ws[j]);
			}
			return cnt;
		}
	}
	return cnt;
}

void findTreasure (int N) {
    dfs (1, 1, N, N);

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (map[i][j])
				Report(i, j);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:63:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         my_assert(strlen(A[i]+1) == N, "each line of the map must contain N zeroes or ones (before loop)");
                                  ^

• Subtask 1: 45 / 100