제출 #133773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133773		nmnm106803	보물 찾기 (CEOI13_treasure2)	C++14	32 / 100	3 ms	380 KiB

treasure

#include "treasure.h"

int cnt;
int chk[105][105];
int n;

void search(int r1, int c1, int r2, int c2, int mod)//짝이면 세로로 나눔, 홀이면 가로로 나눔
{
	if (cnt <= 0) return;

	if (mod % 2 == 0)
	{
		int mid = c1 + (c2 - c1) / 2;
		int blocks = (mid - c1+1)*(r2 - r1+1);
		if (blocks > 0)
		{
			int treasures = countTreasure(r1, c1, r2, mid);
			if (blocks == treasures)
			{
				cnt -= treasures;
				for (int i = r1; i <= r2; i++)
				{
					for (int j = c1; j <= mid; j++)
						chk[i][j] = true;
				}
			}
			else if(treasures!=0)
			{
				search(r1, c1, r2, mid, mod + 1);
			}
		}

		blocks = (c2 - mid)*(r2 - r1+1);
		if (blocks > 0)
		{
			int treasures = countTreasure(r1, mid + 1, r2, c2);
			if (blocks == treasures)
			{

				cnt -= treasures;
				for (int i = r1; i <= r2; i++)
				{
					for (int j = mid + 1; j <= c2; j++)
						chk[i][j] = true;
				}
			}
			else if (treasures != 0)
			{
				search(r1, mid + 1, r2, c2, mod + 1);
			}
		}
	}
	else
	{
		int mid = r1 + (r2 - r1) / 2;
		int blocks = (c2 - c1+1)*(mid - r1+1);
		if (blocks > 0)
		{
			int treasures = countTreasure(r1, c1, mid, c2);
			if (blocks == treasures)
			{

				cnt -= treasures;
				for (int i = r1; i <= mid; i++)
				{
					for (int j = c1; j <= c2; j++)
						chk[i][j] = true;
				}
			}
			else if (treasures != 0)
			{
				search(r1, c1, mid, c2, mod + 1);
			}
		}

		blocks = (r2 - mid)*(c2 - c1+1);
		if (blocks > 0)
		{
			int treasures = countTreasure(mid + 1, c1, r2, c2);
			if (blocks == treasures)
			{
				cnt -= treasures;
				for (int i = mid + 1; i <= r2; i++)
				{
					for (int j = c1; j <= c2; j++)
						chk[i][j] = true;
				}
			}
			else if(treasures != 0)
			{
				search(mid + 1, c1, r2, c2, mod + 1);
			}
		}
	}
}

void init()
{

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			chk[i][j] = false;

}
void findTreasure(int N) {
	n = N;
	cnt = countTreasure(1, 1, N, N);
	if (!cnt) return;

	init();
	search(1, 1, n, n, 0);

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
			if (chk[i][j]) Report(i, j);
	}
}

• Subtask 1: 32 / 100