oj.uz

답안 #4533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4533 2013-10-22T03:52:14 Z kriii 보물 찾기 (CEOI13_treasure2) C++
0 / 100
 0 ms 1784 KB 
#include "treasure.h"
#include <map>
using namespace std;

map<pair<int, int>, int> mem;

int RN,T[111][111],R[111][111],D[111][111];

int get(int x1, int y1, int x2, int y2)
{
	if (x1 > RN || y1 > RN) return 0;
	while (x2 > RN) x2--;
	while (y2 > RN) y2--;

	int z1 = D[x1][y1], z2 = D[x2][y2];

	if (!mem.count(make_pair(z1,z2))) mem[make_pair(z1,z2)] = countTreasure(x1,y1,x2,y2);
	return mem[make_pair(z1,z2)];
}

void findTreasure (int N)
{
	int i,j,h,c=0;
	for (i=1;i<=N;i++) for (j=1;j<=N;j++) R[i][j] = 0;
	for (i=1;i<=N;i++) for (j=i;j<=N;j++) D[i][j] = ++c;

	RN = N;

	if (N % 2) N++;
	h = N / 2;

	for (i=1;i<=h+1;i++) for (j=1;j<=h+1;j++) T[i][j] = get(i,j,N,N);
	for (i=1;i<=h;i++) for (j=1;j<=h;j++) R[i][j] = T[i][j] - T[i+1][j] - T[i][j+1] + T[i+1][j+1];

	for (i=h;i<=N;i++) for (j=h;j<=N;j++) T[i][j] = get(1,1,i,j);
	for (i=h+1;i<=N;i++) for (j=h+1;j<=N;j++) R[i][j] = T[i][j] - T[i-1][j] - T[i][j-1] + T[i-1][j-1];

	for (i=1;i<=h;i++) for (j=h+1;j<=N;j++) T[i][j] = get(i,1,N,j);
	for (i=1;i<h;i++) for (j=h+2;j<=N;j++) R[i][j] = T[i][j] - T[i+1][j] - T[i][j-1] + T[i+1][j-1];

	for (i=h+1;i<=N;i++) for (j=1;j<=h;j++) T[i][j] = get(1,j,i,N);
	for (i=h+2;i<=N;i++) for (j=1;j<h;j++) R[i][j] = T[i][j] - T[i-1][j] - T[i][j+1] + T[i-1][j+1];

	for (j=1;j<h;j++){
		c = get(1,j,N,N)-get(1,j+1,N,N);
		for (i=1;i<=N;i++) c -= R[i][j];
		R[h+1][j] = c;
	}

	for (j=h+1;j<=N;j++){
		c = get(1,1,N,j)-get(1,1,N,j-1);
		for (i=1;i<=N;i++) c -= R[i][j];
		R[h][j] = c;
	}

	for (i=1;i<h;i++){
		c = get(i,1,N,N) - get(i+1,1,N,N);
		for (j=1;j<=N;j++) c -= R[i][j];
		R[i][h+1] = c;
	}

	for (i=h+1;i<=N;i++){
		c = get(1,1,i,N) - get(1,1,i-1,N);
		for (j=1;j<=N;j++) c -= R[i][j];
		R[i][h] = c;
	}

	c = get(1,1,N,h);
	for (i=1;i<=N;i++) for (j=1;j<=h;j++) c -= R[i][j];
	R[h+1][h] = c;

	c = get(1,h+1,N,N);
	for (i=1;i<=N;i++) for (j=h+1;j<=N;j++) c -= R[i][j];
	R[h][h+1] = c;

	for (i=1;i<=RN;i++) for (j=1;j<=RN;j++) if(R[i][j] == 1) Report(i, j);
}

Compilation message

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
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1388 KB Error - not all of the treasure cells have been reported
2 Incorrect 0 ms 1388 KB Invalid Access
3 Incorrect 0 ms 1388 KB Invalid Access
4 Incorrect 0 ms 1388 KB Invalid Access
5 Incorrect 0 ms 1520 KB Error - not all of the treasure cells have been reported
6 Incorrect 0 ms 1520 KB Error - not all of the treasure cells have been reported
7 Incorrect 0 ms 1652 KB Error - not all of the treasure cells have been reported
8 Incorrect 0 ms 1652 KB Invalid Access
9 Incorrect 0 ms 1652 KB Error - not all of the treasure cells have been reported
10 Incorrect 0 ms 1784 KB Error - not all of the treasure cells have been reported