oj.uz

Submission #42483

# Submission time Handle Problem Language Result Execution time Memory
42483 2018-02-27T17:01:21 Z zaqq1414 Treasure (different grader from official contest) (CEOI13_treasure2) C++14
68 / 100
 2 ms 788 KB 
#include "treasure.h"
#define MAX	101

int cache[MAX][MAX];	// 해당 좌표 treasure 유무
int log[4][MAX][MAX];	// 기준 좌표에서 해당 좌표까지 treasurer 개수
int size;

int myCountTreasure(int side, int i, int j) {
	int &ret = log[side - 1][i][j];
	if (ret == -1) {
		if (side == 1) {	// 1사분면
			return ret = countTreasure(i, j, size, size);
		}
		else if (side == 2) {	// 2사분면
			return ret = countTreasure(i, 1, size, j);
		}
		else if (side == 3) {	// 3사분면
			return ret = countTreasure(1, j, i, size);
		}
		else { // 4사분면
			return  ret = countTreasure(1, 1, i, j);
		}
	}
	else
		return ret;
}

void side1dp() {
	for (int i = size / 2 - 1; i > 0; i--)
		cache[i][size / 2 - 1] = myCountTreasure(1, i, size / 2 - 1) - myCountTreasure(1, i + 1, size / 2 - 1) - myCountTreasure(1, i, size / 2) + myCountTreasure(1, i + 1, size / 2);
	for (int j = size / 2 - 1; j > 0; j--)
		cache[size / 2 - 1][j] = myCountTreasure(1, size / 2 - 1, j) - myCountTreasure(1, size / 2 - 1, j + 1) - myCountTreasure(1, size / 2, j) + myCountTreasure(1, size / 2, j + 1);

	for (int i = size / 2 - 2; i > 0; i--) {
		for (int j = size / 2 - 2; j > 0; j--) {
			cache[i][j] = myCountTreasure(1, i, j) - log[0][i + 1][j] - log[0][i][j + 1] + log[0][i + 1][j + 1];
		}
	}
}

void side2dp() {
	for (int i = size / 2 - 1; i > 0; i--)
		cache[i][size / 2] = myCountTreasure(2, i, size / 2) - myCountTreasure(2, i + 1, size / 2) - myCountTreasure(2, i, size / 2 - 1) + myCountTreasure(2, i + 1, size / 2 - 1);
	for (int j = size / 2; j <= size; j++)
		cache[size / 2 - 1][j] = myCountTreasure(2, size / 2 - 1, j) - myCountTreasure(2, size / 2 - 1, j - 1) - myCountTreasure(2, size / 2, j) + myCountTreasure(2, size / 2, j - 1);

	for (int i = size / 2 - 2; i > 0; i--) {
		for (int j = size / 2 + 1; j <= size; j++) {
			cache[i][j] = myCountTreasure(2, i, j) - log[1][i + 1][j] - log[1][i][j - 1] + log[1][i + 1][j - 1];
		}
	}
}

void side3dp() {
	for (int i = size / 2; i <= size; i++)
		cache[i][size / 2 - 1] = myCountTreasure(3, i, size / 2 - 1) - myCountTreasure(3, i - 1, size / 2 - 1) - myCountTreasure(3, i, size / 2) + myCountTreasure(3, i - 1, size / 2);
	for (int j = size / 2 - 1; j > 0; j--)
		cache[size / 2][j] = myCountTreasure(3, size / 2, j) - myCountTreasure(3, size / 2, j + 1) - myCountTreasure(3, size / 2 - 1, j) + myCountTreasure(3, size / 2 - 1, j + 1);

	for (int i = size / 2 + 1; i <= size; i++) {
		for (int j = size / 2 - 2; j > 0; j--) {
			cache[i][j] = myCountTreasure(3, i, j) - log[2][i - 1][j] - log[2][i][j + 1] + log[2][i - 1][j + 1];
		}
	}
}

void side4dp() {
	for (int i = size / 2; i <= size; i++)
		cache[i][size / 2] = myCountTreasure(4, i, size / 2) - myCountTreasure(4, i - 1, size / 2) - myCountTreasure(4, i, size / 2 - 1) + myCountTreasure(4, i - 1, size / 2 - 1);
	for (int j = size / 2; j <= size; j++)
		cache[size / 2][j] = myCountTreasure(4, size / 2, j) - myCountTreasure(4, size / 2, j - 1) - myCountTreasure(4, size / 2 - 1, j) + myCountTreasure(4, size / 2 - 1, j - 1);

	for (int i = size / 2 + 1; i <= size; i++) {
		for (int j = size / 2 + 1; j <= size; j++) {
			cache[i][j] = myCountTreasure(4, i, j) - myCountTreasure(4, i - 1, j) - myCountTreasure(4, i, j - 1) + myCountTreasure(4, i - 1, j - 1);
		}
	}
}

void dp() {
	if (size > 1) {
		cache[1][1] = myCountTreasure(4, size, size) - countTreasure(1, 2, size, size) - countTreasure(2, 1, size, size) + countTreasure(2, 2, size, size);
		log[3][1][1] = cache[1][1];
	}
	else {
		cache[1][1] = countTreasure(1, 1, 1, 1);
		return;
	}

	for (int i = 2; i <= size; i++)
		cache[i][1] = myCountTreasure(4, i, 1) - log[3][i - 1][1];
	for (int j = 2; j <= size; j++)
		cache[1][j] = myCountTreasure(4, 1, j) - log[3][1][j - 1];

	for (int i = 2; i <= size; i++) {
		for (int j = 2; j <= size; j++) {
			cache[i][j] = myCountTreasure(4, i, j) - log[3][i - 1][j] - log[3][i][j - 1] + log[3][i - 1][j - 1];
		}
	}
}

void findTreasure (int N) {
	// Initialize
	size = N;
	for (int i = 1; i <= size; i++)
		for (int j = 1; j <= size; j++) {
			for (int s = 0; s < 4; s++)
				log[s][i][j] = -1;
		}

	if (size > 10) {
		side1dp();
		side2dp();
		side3dp();
		side4dp();
	}
	else {
		dp();
	}

	for (int i = 1; i <= size; i++)
		for (int j = 1; j <= size; j++)
			if (cache[i][j])
				Report(i, j);
	return;
}

Compilation message

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
68.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 376 KB Output is partially correct - N = 5, K = 422, score = 8
2 Partially correct 1 ms 376 KB Output is partially correct - N = 10, K = 7017, score = 4
3 Partially correct 1 ms 424 KB Output is partially correct - N = 15, K = 29593, score = 4
4 Partially correct 1 ms 440 KB Output is partially correct - N = 16, K = 37043, score = 4
5 Partially correct 2 ms 568 KB Output is partially correct - N = 55, K = 4313673, score = 8
6 Partially correct 1 ms 664 KB Output is partially correct - N = 66, K = 8823543, score = 8
7 Partially correct 2 ms 728 KB Output is partially correct - N = 77, K = 16215530, score = 8
8 Partially correct 2 ms 788 KB Output is partially correct - N = 88, K = 27462779, score = 8
9 Partially correct 2 ms 788 KB Output is partially correct - N = 99, K = 43785193, score = 8
10 Partially correct 2 ms 788 KB Output is partially correct - N = 100, K = 45543203, score = 8