Submission #86160

#	Time	Username	Problem	Language	Result	Execution time	Memory
86160		faceless	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	61 / 100	2 ms	648 KiB

treasure

#include "treasure.h"
bool c[120][120];

int find2 (int r1, int c1, int r2, int c2, int cnt = -1) {
	if (cnt == -1)
		cnt = countTreasure (r1, c1, r2 - 1, c2 - 1);
	if (cnt == 0)
		return cnt;
	if (cnt == (r2 - r1) * (c2 - c1)) {
		for (int j = c1; j < c2; j++)
			c[r1][j] = 1;
		return cnt;
	}
	int mid = (c1 + c2) >> 1;
	int x = find2 (r1, c1, r2, mid);
	find2 (r1, mid, r2, c2, cnt - x);
	return cnt;
}

int find (int r1, int c1, int r2, int c2, int cnt = -1) {
	if (cnt == -1)
		cnt = countTreasure (r1, c1, r2 - 1, c2 - 1);
	if (cnt == 0)
		return cnt;
	if (cnt == (r2 - r1) * (c2 - c1)) {
		for (int i = r1; i < r2; i++)
			for (int j = c1; j < c2; j++)
				c[i][j] = 1;
		return cnt;
	}
	if (r1 + 1 == r2) {
		find2 (r1, c1, r2, c2, cnt);
		return cnt;
	}
	int mid = (r1 + r2) >> 1;
	int x = find (r1, c1, mid, c2);
	find (mid, c1, r2, c2, cnt - x);
	return cnt;
}

void findTreasure (int N) {
	find (1, 1, N + 1, N + 1);	
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (c[i][j])
				Report (i, j);
}

• Subtask 1: 61 / 100