oj.uz

Submission #40600

# Submission time Handle Problem Language Result Execution time Memory
40600 2018-02-05T08:18:38 Z didwlvv Treasure (different grader from official contest) (CEOI13_treasure2) C++14
53 / 100
 2 ms 552 KB 
#include "treasure.h"

int cnt;
int _map[105][105];

void init(int n) {
	cnt = 0;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			_map[i][j] = 0;

}

int dnc(int ly, int lx, int ry, int rx, int t) {
	if (ly == ry && lx == rx) {//한 칸 일때
		if (t) {
			_map[ly][lx] = 1;
			return 1;
		}
		return 0;
	}
	int tmp = t;
	int total = (ry - ly + 1)*(rx - lx + 1);
	if (tmp == total) {
		for (int i = ly; i <= ry; i++) {
			for (int j = lx; j <= rx; j++) {
				_map[i][j] = 1;
			}
		}
		return tmp;
	}

	int midy = (ly + ry) / 2;
	int midx = (lx + rx) / 2;
	int now_cnt = 0;
	int total_le = (ry - ly + 1)*(midx - lx + 1);
	int h_le = countTreasure(ly, lx, ry, midx);
	bool ok = true, ok1 = true;

	if (h_le == total_le) {
		ok = false;
		for (int i = ly; i <= ry; i++) {
			for (int j = lx; j <= midx; j++) {
				_map[i][j] = 1;
			}
		}
		now_cnt += total_le;
	}
	else if (tmp - h_le == total - total_le) {
		ok1 = false;
		for (int i = ly; i <= ry; i++) {
			for (int j = midx + 1; j <= rx; j++) {
				_map[i][j] = 1;
			}
		}
		now_cnt += total - total_le;
	}
	else if (h_le == 0) {
		ok = false;
	}
	else if (tmp - h_le == 0) {
		ok1 = false;
	}
	int f = countTreasure(ly, lx, midy, midx);
	if (ok && now_cnt < tmp)now_cnt += dnc(ly, lx, midy, midx, f);

	if (ok1 && now_cnt < tmp)now_cnt += dnc(ly, midx + 1, midy, rx, countTreasure(ly, lx, midy, rx) - f);

	if (ok && now_cnt < tmp)now_cnt += dnc(midy + 1, lx, ry, midx, h_le - f);

	if (ok1 && now_cnt < tmp)now_cnt += dnc(midy + 1, midx + 1, ry, rx, tmp - now_cnt);
	return now_cnt;

}
void findTreasure(int N) {
	init(N);
	//cnt = countTreasure(1, 1, N, N);
	dnc(1, 1, N, N, countTreasure(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

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

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 248 KB Output is partially correct - N = 5, K = 513, score = 8
2 Partially correct 2 ms 352 KB Output is partially correct - N = 10, K = 8231, score = 1
3 Correct 1 ms 388 KB Output is correct - N = 15, K = 22174, score = 10
4 Correct 1 ms 404 KB Output is correct - N = 16, K = 18182, score = 10
5 Partially correct 2 ms 456 KB Output is partially correct - N = 55, K = 8132239, score = 1
6 Partially correct 2 ms 528 KB Output is partially correct - N = 66, K = 16380026, score = 1
7 Correct 2 ms 548 KB Output is correct - N = 77, K = 7320765, score = 10
8 Correct 2 ms 548 KB Output is correct - N = 88, K = 9601001, score = 10
9 Partially correct 2 ms 548 KB Output is partially correct - N = 99, K = 88700711, score = 1
10 Partially correct 2 ms 552 KB Output is partially correct - N = 100, K = 93421435, score = 1