oj.uz

답안 #130827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130827 2019-07-16T06:42:05 Z yeonwan 보물 찾기 (CEOI13_treasure2) C++14
44 / 100
 2 ms 508 KB 
#include "treasure.h"
//#include<iostream>
//using namespace std;
int ans[103][103];
int sum[103][103];

void exhaustive_Search(int N) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) if (countTreasure(i, j, i, j)) ans[i][j] = 1;
	}
}


void recursively_find(int a, int b, int c, int d) { //(a,b) ~ (c,d) 까지.	
	int cnt = countTreasure(a, b, c, d);
	if (cnt == 0) return;
	if ((a - c) + (b - d) == 1 && cnt == 1) {
		if (countTreasure(a, b, a, b)) ans[a][b] = 1;
		else ans[c][d] = 1;
		return;
	}

	if (cnt == (c - a + 1) * (d - b + 1)) {
		for (int i = a; i <= c; i++) {
			for (int j = b; j <= d; j++) ans[i][j] = 1;
		}
		return;
	}
	
	if (a == c && b == d) return;
	
	int depth = c - a ;
	int width = d - b ;
	
	if (depth >= width) {  // 세로 >= 가로
		
		recursively_find(a, b, a + depth/2, d);
		recursively_find(a + depth/2+1, b , c, d);
	}
	else { // 가로 > 세로
		recursively_find(a, b, c,  b+ width/2 );
		recursively_find(a, b + width/2 + 1 , c, d);
	}
	
}

void findbyArea(int N) {
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			sum[i][j] = countTreasure(1, 1, i, j);
			ans[i][j] = sum[i][j] - sum[i - 1][j] - sum[i][j - 1] + sum[i - 1][j - 1];
		}
	}

}



void findTreasure(int N) {
	//recursively_find(1, 1, N, N);
	//exhaustive_Search(N);
	findbyArea(N);
	

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

Subtask #1
44.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 252 KB Output is partially correct - N = 5, K = 425, score = 8
2 Partially correct 2 ms 376 KB Output is partially correct - N = 10, K = 7075, score = 4
3 Partially correct 2 ms 376 KB Output is partially correct - N = 15, K = 36450, score = 4
4 Partially correct 2 ms 376 KB Output is partially correct - N = 16, K = 47296, score = 4
5 Partially correct 2 ms 376 KB Output is partially correct - N = 55, K = 6782050, score = 4
6 Partially correct 2 ms 376 KB Output is partially correct - N = 66, K = 14090571, score = 4
7 Partially correct 2 ms 376 KB Output is partially correct - N = 77, K = 26140961, score = 4
8 Partially correct 2 ms 504 KB Output is partially correct - N = 88, K = 44642224, score = 4
9 Partially correct 2 ms 508 KB Output is partially correct - N = 99, K = 71566902, score = 4
10 Partially correct 2 ms 504 KB Output is partially correct - N = 100, K = 74507500, score = 4