Submission #41039

#	Time	Username	Problem	Language	Result	Execution time	Memory
41039		kdk8361	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	44 / 100	2 ms	632 KiB

treasure

#include "treasure.h"

struct treasure {
	int x[10001], y[10001], idx;
	treasure() {
		for (int i = 0; i < 10001; i++) x[i] = y[i] = 0;
		idx = 0;
	}
	void init() { idx = 0; }
	void push(int ax, int ay) {
		x[idx] = ax;
		y[idx] = ay;
		idx++;
	}
	void report() {
		for (int i = 0; i < idx; i++)
			Report(x[i], y[i]);
	}
};

treasure gogo;

int getArea(int x1, int y1, int x2, int y2) {
	return (x2 - (x1 - 1))*(y2 - (y1 - 1));
}

void dnq(int x1, int y1, int x2, int y2, int cnt) {
	int siz = getArea(x1, y1, x2, y2);
	if (cnt == siz) {
		for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++)
			gogo.push(i, j);
		return;
	}
	else if (cnt == 0) return;
	int sum, r1, r2, r3, r4, ar1, ar2, ar3, ar4;
	sum = r1 = r2 = r3 = r4 = ar1 = ar2 = ar3 = ar4 = 0;

	if (cnt > siz / 2) {
		// 4분할
		int xmid = (x1 + x2) / 2;
		int ymid = (y1 + y2) / 2;
		
		r1 = countTreasure(x1, y1, xmid, ymid);
		if (r1) dnq(x1, y1, xmid, ymid, r1);
		sum += r1;
		if (sum == cnt) return;
		ar1 = getArea(x1, y1, xmid, ymid);
		siz -= ar1;
		// 남은지역 전체가 보물이라면
		if (siz == cnt - sum) {
			// 전부 보고
			for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) {
				if (i <= xmid && j <= ymid) continue;
					gogo.push(i, j);
			}
			return;
		}

		r2 = countTreasure(x1, ymid + 1, xmid, y2);
		if (r2) dnq(x1, ymid + 1, xmid, y2, r2);
		sum += r2;
		if (sum == cnt) return;
		ar2 = getArea(x1, ymid + 1, xmid, y2);
		siz -= ar2;
		// 남은지역 전체가 보물이라면
		if (siz == cnt - sum) {
			// 전부 보고
			for (int i = xmid + 1; i <= x2; i++) for (int j = y1; j <= y2; j++)
				gogo.push(i, j);
			return;
		}

		r3 = countTreasure(xmid + 1, y1, x2, ymid);
		if (r3) dnq(xmid + 1, y1, x2, ymid, r3);
		sum += r3;
		if (sum == cnt) return;
		ar3 = getArea(xmid + 1, y1, x2, ymid);
		siz -= ar3;
		// 남은지역 전체가 보물이라면
		if (siz == cnt - sum) {
			// 전부 보고
			for (int i = xmid + 1; i <= x2; i++) for (int j = ymid + 1; j <= y2; j++)
				gogo.push(i, j);
			return;
		}

		r4 = countTreasure(xmid + 1, ymid + 1, x2, y2);
		if (r4) dnq(xmid + 1, ymid + 1, x2, y2, r4);
	}
	else {
		if (x2 - (x1 - 1) >= y2 - (y1 - 1)) {
			//x축 자르기
			int xmid = (x1 + x2) / 2;
			r1 = countTreasure(x1, y1, xmid, y2);
			if (r1) dnq(x1, y1, xmid, y2, r1);
			sum += r1;
			if (sum == cnt) return;
			ar1 = getArea(x1, y1, xmid, y2);
			siz -= ar1;
			// 남은지역 전체가 보물이라면
			if (siz == cnt - sum) {
				// 전부 보고
				for (int i = xmid + 1; i <= x2; i++) for (int j = y1; j <= y2; j++) 
					gogo.push(i, j);
				return;
			}

			r2 = countTreasure(xmid + 1, y1, x2, y2);;
			if (r2) dnq(xmid + 1, y1, x2, y2, r2);

		}
		else {
			int ymid = (y1 + y2) / 2;
			r1 = countTreasure(x1, y1, x2, ymid);
			if (r1) dnq(x1, y1, x2, ymid, r1);
			sum += r1;
			if (sum == cnt) return;
			ar1 = getArea(x1, y1, x2, ymid);
			siz -= ar1;
			// 남은지역 전체가 보물이라면
			if (siz == cnt - sum) {
				// 전부 보고
				for (int i = x1; i <= x2; i++) for (int j = ymid + 1; j <= y2; j++)
					gogo.push(i, j);
				return;
			}

			r2 = countTreasure(x1, ymid + 1, x2, y2);
			if (r2) dnq(x1, ymid + 1, x2, y2, r2);
		}
	}
}


void findTreasure (int N) {
    int cnt = countTreasure(1, 1, N, N);
	if (cnt == 0) return;
	dnq(1, 1, N, N, cnt);
	gogo.report();
}

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: 44 / 100