제출 #44820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44820		tjd229	보물 찾기 (CEOI13_treasure2)	C++11	72 / 100	3 ms	776 KiB

treasure

#include "treasure.h"
const int bnd = 1 << 7;
int ans_r[100 * 100];
int ans_c[100 * 100];
int ix;
int ft[bnd+1][bnd+1];
void update(int x,int y){
	while (y <=bnd){
		int _x = x;
		while (_x <=bnd){
			ft[y][_x] += 1;
			_x += (_x&-_x);
		}
		y += (y&-y);
	}
}
int sum(int x, int y){	
	//if (x == 0 || y == 0) return 0;
	int res = 0;
	while (y >0){
		int _x = x;
		while (_x >0){
			res += ft[y][_x];
			
			_x -= (_x&-_x);
		}
		y -= (y&-y);
	}
	return res;
}
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;
				update(i, j);
			}
		}
		return;
	}
	int rc = (r1 + r2) >> 1;
	int cc = (c1 + c2) >> 1;

	int subcnt = countTreasure(1, 1, rc, cc);
	grid -= (rc - r1 + 1)*(cc - c1 + 1);
	subcnt -= sum(rc, cc);
	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(1,1, r2, cc);
			subcnt -= sum(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(1, 1, rc, c2);
			subcnt -= sum(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]);
}

컴파일 시 표준 에러 (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: 72 / 100