oj.uz

답안 #4534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4534 2013-10-22T04:04:05 Z kriii 보물 찾기 (CEOI13_treasure2) C++
40 / 100
 3 ms 2048 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)
{
	int z1 = D[x1][x2], z2 = D[y1][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;

	h = N / 2;

	if (N % 2){

	}
	else{
		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+2;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+2;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
40.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 Output is partially correct - N = 10, K = 4653, score = 8
3 Incorrect 0 ms 1388 KB Error - not all of the treasure cells have been reported
4 Incorrect 0 ms 1388 KB Output is partially correct - N = 16, K = 29379, score = 8
5 Incorrect 0 ms 1388 KB Error - not all of the treasure cells have been reported
6 Incorrect 0 ms 1652 KB Output is partially correct - N = 66, K = 8313429, score = 8
7 Incorrect 0 ms 1388 KB Error - not all of the treasure cells have been reported
8 Incorrect 3 ms 1916 KB Output is partially correct - N = 88, K = 26257971, score = 8
9 Incorrect 0 ms 1388 KB Error - not all of the treasure cells have been reported
10 Incorrect 3 ms 2048 KB Output is partially correct - N = 100, K = 43777503, score = 8