Submission #44818

#	Time	Username	Problem	Language	Result	Execution time	Memory
44818		tjd229	Treasure (different grader from official contest) (CEOI13_treasure2)	C++11	56 / 100	3 ms	756 KiB

treasure

#include "treasure.h"
int ans_r[100 * 100];
int ans_c[100 * 100];
int ix;
void search(int cnt,int r1,int c1,int r2,int c2){
	int grid = (r2 - r1 + 1)*(c2 - c1 + 1);
	if (grid == cnt){
		//All report
		int i, j;
		for (i = r1; i <= r2; i++){
			for (j = c1; j <= c2; j++){
				ans_r[ix] = i;
				ans_c[ix++] = j;
			}
		}
		return;
	}
	int rc = (r1 + r2) >> 1;
	int cc = (c1 + c2) >> 1;

	int subcnt = countTreasure(r1, c1, rc, cc);
	grid -= (rc - r1 + 1)*(cc - c1 + 1);
	if (subcnt != 0) search(subcnt, r1, c1, rc, cc);
	cnt -= subcnt;
	if (cnt == 0) return;

	if (rc + 1 <= r2){
		if (grid == cnt) subcnt = (r2 - rc - 1 + 1)*(cc - c1 + 1);
		else
			subcnt = countTreasure(rc + 1, c1, r2, cc);
		grid -= (r2 - rc - 1 + 1)*(cc - c1 + 1);
		if (subcnt != 0) search(subcnt, rc + 1, c1, r2, cc);
		cnt -= subcnt;
		if (cnt == 0) return;
	}

	if (cc + 1 <= c2){
		if (grid == cnt) subcnt = (rc - r1 + 1)*(c2 - cc - 1 + 1);
		else
			subcnt = countTreasure(r1, cc + 1, rc, c2);
		grid -= (rc - r1 + 1)*(c2 - cc - 1 + 1);
		if (subcnt != 0) search(subcnt, r1, cc + 1, rc, c2);
		cnt -= subcnt;
		if (cnt == 0) return;
	}
	if (rc+1<=r2&&cc+1<=c2)
		search(cnt, rc+1, cc + 1, r2, c2);
}
void findTreasure(int N) {
	ix = 0;
	int cnt = countTreasure(1, 1, N, N);
	if (cnt > 0) search(cnt, 1, 1, N, N);
	while (ix--) Report(ans_r[ix],ans_c[ix]);
}

Compilation message (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: 56 / 100