oj.uz

Submission #4538

# Submission time Handle Problem Language Result Execution time Memory
4538 2013-10-22T05:41:02 Z kriii Treasure (different grader from official contest) (CEOI13_treasure2) C++
100 / 100
 3 ms 2052 KB 
#include "treasure.h"
#include <map>
using namespace std;

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

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

void add(int x1, int y1, int x2, int y2, int c)
{
	int z1 = D[x1][x2], z2 = D[y1][y2];

	mem[make_pair(z1,z2)] = c;
}

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;

	h = (N + 1) / 2;
	mem.clear();

	if (N % 2){
		for (i=1;i<=h;i++) for (j=1;j<=h;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];

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

		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;j<=N;j++) T[i][j] = get(i,1,N,j);
		for (i=1;i<h;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=h;i<=N;i++) for (j=1;j<=h;j++) T[i][j] = get(1,j,i,N);
		for (i=h+1;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][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] = 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,N);
		for (i=1;i<=N;i++) for (j=1;j<=N;j++) c -= R[i][j];
		R[h][h] = c;
	}
	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=2;i<=h+1;i++) add(1,1,i-1,N,T[1][1]-T[i][1]);
		for (j=2;j<=h+1;j++) add(1,1,N,j-1,T[1][1]-T[1][j]);

		c = 0;
		for (i=1;i<=h;i++) for (j=1;j<=h;j++) c += R[i][j];
		add(1,1,h,h,c);

		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<=N;i++) for (j=1;j<=N;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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1392 KB Output is correct - N = 5, K = 289, score = 10
2 Correct 0 ms 1392 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 0 ms 1392 KB Output is correct - N = 15, K = 22289, score = 10
4 Correct 0 ms 1392 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 0 ms 1656 KB Output is correct - N = 55, K = 4005289, score = 10
6 Correct 0 ms 1656 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 0 ms 1788 KB Output is correct - N = 77, K = 15383161, score = 10
8 Correct 3 ms 1920 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 3 ms 2052 KB Output is correct - N = 99, K = 42032201, score = 10
10 Correct 0 ms 2052 KB Output is correct - N = 100, K = 43760000, score = 10