제출 #40815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40815		969	보물 찾기 (CEOI13_treasure2)	C++14	0 / 100	1 ms	392 KiB

treasure

#include "treasure.h"
#include <iostream>
#define MAX 1000000
#define NMAX 102

int count[MAX];
class TREASURE {
public:
	int x, y;
};
int tresureCnt;
TREASURE treasure[NMAX * NMAX];

int sum[NMAX][NMAX];
int memo[NMAX][NMAX][NMAX][NMAX];


int myCountTreasure(int r1, int c1, int r2, int c2) {
	if (memo[r1][c1][r2][c2] == -1) {
		memo[r1][c1][r2][c2] = countTreasure(r1, c1, r2, c2);
	}
	return memo[r1][c1][r2][c2];
}

void findTreasure (int N) {
    // 전체 보물의 수
	int cnt = countTreasure(1, 1, N, N);
	count[0] = cnt;
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				for (int l = 1; l <= N; l++) {
					memo[i][j][k][l] = -1;
				}
			}
		}
	}

	for (int i = 1; i <= N / 2; i++) {
		for (int j = 1; j <= N / 2; j++) {
			sum[i][j] = cnt - myCountTreasure(i + 1, 1, N, N) - myCountTreasure(1, j + 1, N, N) + myCountTreasure(i + 1, j + 1, N, N);
			sum[i][N - j + 1] = cnt - myCountTreasure(1, 1, N, N - j) - myCountTreasure(i + 1, 1, N, N) + myCountTreasure(i + 1, 1, N, N - j);
			sum[N - i + 1][j] = cnt - myCountTreasure(1, 1, N - i, N) - myCountTreasure(1, j + 1, N, N) + myCountTreasure(1, j + 1, N - i, N);
			sum[N - i + 1][N - j + 1] = cnt - myCountTreasure(1, 1, N - i, N) - myCountTreasure(1, 1, N, N - j) + myCountTreasure(1, 1, N - i, N - j);
		}
	}

	/*for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%3d", sum[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	*/
	for (int i = 0; i < N / 2; i++) {
		for(int j = 1; j <= N; j++){
			sum[N / 2 - i][j] -= sum[N / 2 - i - 1][j];
			sum[N / 2 + i + 1][j] -= sum[N / 2 + i + 2][j];
		}
	}

	/*for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%3d", sum[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < N / 2; j++) {
			sum[i][N / 2 - j] -= sum[i][N / 2 - j - 1];
			sum[i][N / 2 + j + 1] -= sum[i][N / 2 + j + 2];
		}
	}

	/*for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%3d", sum[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/

	if (cnt > 0) {
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (sum[i][j] == 1) Report(i, j);
	}
}


//void recursive(int y, int x, int N, int k) {
//	if (N == 1) {
//		treasure[tresureCnt++] = { x, y };
//		return;
//	}
//	count[k * 4 + 1] = countTreasure(y, x, y + (N + 1) / 2 - 1, x + (N + 1) / 2 - 1);
//	if (count[k * 4 + 1] != count[k]) count[k * 4 + 2] = countTreasure(y, x, y + (N + 1) / 2 - 1, x + N - 1) - count[4 * k + 1];
//	if (count[k * 4 + 1] + count[4 * k + 2] != count[k]) count[k * 4 + 3] = countTreasure(y, x, y + N - 1, x + (N + 1) / 2 - 1) - count[4 * k + 1];
//	count[k * 4 + 4] = count[k] - count[k * 4 + 1] - count[k * 4 + 2] - count[k * 4 + 3];
//	if (count[k * 4 + 1] != 0) {
//		recursive(y, x, (N + 1) / 2, 4 * k + 1);
//	}
//	if (count[k * 4 + 2] != 0) {
//		recursive(y, x + (N + 1) / 2, N / 2, k * 4 + 2);
//	}
//	if (count[k * 4 + 3] != 0) {
//		recursive(y + (N + 1) / 2, x, N / 2, k * 4 + 3);
//	}
//	if (count[k * 4 + 4] != 0) {
//		recursive(y + (N + 1) / 2, x + (N + 1) / 2, N / 2, k * 4 + 4);
//	}
//}

컴파일 시 표준 에러 (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: 0 / 100