Submission #94795

#	Time	Username	Problem	Language	Result	Execution time	Memory
94795		newyear	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	69 / 100	2 ms	504 KiB

treasure

#include "treasure.h"

int map[101][101], sum[4][101][101];

int mycount(int r1, int c1, int r2, int c2, int mode) {
	int row = r2 - r1+1, col = c2 - c1+1;
	if (!mode) {
		if (sum[mode][r2][c2]) return sum[mode][r2][c2];
		sum[mode][r2][c2] = countTreasure(r1, c1, r2, c2);
		if (sum[mode][r2][c2] == row*col) {
			for (int i = r1; i <= r2; i++)
				for (int j = c1; j <= c2; j++)
					map[i][j] = 1;
		}
		return sum[mode][r2][c2];
	}
	else if (mode == 1) {
		if (sum[mode][r1][c1]) return sum[mode][r1][c1];
		sum[mode][r1][c1] = countTreasure(r1, c1, r2, c2);
		if (sum[mode][r1][c1] == row*col) {
			for (int i = r1; i <= r2; i++)
				for (int j = c1; j <= c2; j++)
					map[i][j] = 1;
		}
		return sum[mode][r1][c1];
	}
	else if (mode == 2) {
		if (sum[mode][r1][c2]) return sum[mode][r1][c2];
		sum[mode][r1][c2] = countTreasure(r1, c1, r2, c2);
		if (sum[mode][r1][c2] == row*col) {
			for (int i = r1; i <= r2; i++)
				for (int j = c1; j <= c2; j++)
					map[i][j] = 1;
		}
		return sum[mode][r1][c2];
	}
	else {
		if (sum[mode][r2][c1]) return sum[mode][r2][c1];
		sum[mode][r2][c1] = countTreasure(r1, c1, r2, c2);
		if (sum[mode][r2][c1] == row*col) {
			for (int i = r1; i <= r2; i++)
				for (int j = c1; j <= c2; j++)
					map[i][j] = 1;
		}
		return sum[mode][r2][c1];
	}
}

void findTreasure(int N) {
	for (int i = N; i > N/2; i--)
		for (int j = N; j > N / 2; j--) {
			if (!map[i][j]) map[i][j] = mycount(1, 1, i, j, 0) - mycount(1, 1, i - 1, j, 0) - mycount(1, 1, i, j - 1, 0) + mycount(1, 1, i - 1, j - 1, 0);
		}

	for (int i = 1; i <= N / 2; i++)
		for (int j = 1; j <= N / 2; j++)
			if (!map[i][j]) map[i][j] = mycount(i, j, N, N, 1) - mycount(i, j + 1, N, N, 1) - mycount(i + 1, j, N, N, 1) + mycount(i + 1, j + 1, N, N, 1);

	for (int i = 1; i <= N / 2; i++)
		for (int j = N; j > N / 2; j--)
			if (!map[i][j]) map[i][j] = mycount(i, 1, N, j, 2) - mycount(i, 1, N, j - 1, 2) - mycount(i + 1, 1, N, j, 2) + mycount(i + 1, 1, N, j - 1, 2);

	for (int i = N; i > N / 2; i--)
		for (int j = 1; j <= N / 2; j++)
			if (!map[i][j]) map[i][j] = mycount(1, j, i, N, 3) - mycount(1, j + 1, i, N, 3) - mycount(1, j, i - 1, N, 3) + mycount(1, j + 1, i - 1, N, 3);

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

• Subtask 1: 69 / 100