Submission #53330

# Submission time Handle Problem Language Result Execution time Memory
53330 2018-06-29T12:10:50 Z ics0503 Treasure (different grader from official contest) (CEOI13_treasure2) C++17
100 / 100
2 ms 804 KB
#include "treasure.h"
#include<stdio.h>
//int countTreasure (int r1, int c1, int r2, int c2);
int a[121][121], S[121][121], P[8][121], temp[2][121];
void findTreasure (int n) {
	if (n == 1) {
		if (countTreasure(1, 1, 1, 1))Report(1, 1);
		return;
	}
	int i, j, mx = (n+1) / 2, my = (n+1) / 2;
	for (i = mx + 1; i <= n; i++) for (j = my + 1; j <= n; j++)S[i][j] = countTreasure(1, 1, i, j);
	for (i = mx + 1; i <= n; i++)for (j = 2; j <= my; j++)S[i][j] = countTreasure(1, j, i, n);
	for (i = mx + 1; i <= n; i++)S[i][1] = S[i][n];
	for (i = 2; i <= mx; i++)for (j = my + 1; j <= n; j++)S[i][j] = countTreasure(i, 1, n, j);
	for (j = my + 1; j <= n; j++)S[1][j] = S[n][j];
	for (i = 2; i <= mx; i++)for (j = 2; j <= my; j++)S[i][j] = countTreasure(i, j, n, n);
	for (i = 1; i <= mx; i++)S[i][1] = S[i][n];
	for (j = 1; j <= mx; j++)S[1][j] = S[n][j];
	int all = S[n][n];
	int x1 = countTreasure(1, 1, mx, my);
	for (i = my + 1; i <= n; i++)P[0][i] = countTreasure(1, 1, mx, i);
	for (i = mx + 1; i <= n; i++)P[1][i] = countTreasure(1, 1, i, my);
	P[0][mx] = P[1][mx] = x1;
	P[2][1] = P[0][n];
	int x2 = P[0][n] - x1;
	for (i = 2; i <= mx; i++)P[2][i] = countTreasure(1, i, mx, n);
	for (i = mx + 1; i <= n; i++)P[3][i] = S[i][n] - P[1][i];
	P[2][mx + 1] = P[3][mx] = x2;
	int x3 = P[1][n] - x1;
	int x4 = all - x1 - x2 - x3;
	for (i = 2; i <= mx; i++)P[4][i] = countTreasure(i, mx + 1, n, n);
	P[4][1] = P[3][n];
	for (i = 1; i <= mx; i++)P[5][i] = S[n][i] - P[2][i];
	P[4][mx + 1] = P[5][mx + 1] = x4;

	for (i = mx + 1; i <= n; i++)for (j = mx + 1; j <= n; j++) {
		int A, B, C, D;
		A = S[i][j];
		if (i == mx + 1) B = P[0][j - 1];
		else if (j == mx + 1) B = P[1][i - 1];
		else B = S[i - 1][j - 1];
		if (i == mx + 1) C = P[0][j];
		else C = S[i - 1][j];
		if (j == mx + 1) D = P[1][i];
		else D = S[i][j - 1];
		a[i][j] = A + B - C - D;
	}
	for (i = mx + 1; i <= n; i++)for (j = 1; j <= mx; j++) {
		int A, B, C, D;
		A = S[i][j];
		if (i == mx + 1) B = P[2][j + 1];
		else if (j == mx) B = P[3][i - 1];
		else B = S[i - 1][j + 1];
		if (i == mx + 1) C = P[2][j];
		else C = S[i - 1][j];
		if (j == mx) D = P[3][i];
		else D = S[i][j + 1];
		a[i][j] = A + B - C - D;
	}
	for (i = 1; i <= mx; i++)for (j = 1; j <= mx; j++) {
		int A, B, C, D;
		A = S[i][j];
		if (i == mx) B = P[5][j + 1];
		else if (j == mx) B = P[4][i + 1];
		else B = S[i + 1][j + 1];
		if (i == mx) C = P[5][j];
		else C = S[i + 1][j];
		if (j == mx) D = P[4][i];
		else D = S[i][j + 1];
		a[i][j] = A + B - C - D;
	}
	for (i = n; i >= 1; i--)for (j = 1; j <= n; j++) {
		if (i <= mx&&my < j)continue;
		S[i][j] = S[i + 1][j] + S[i][j - 1] - S[i + 1][j - 1] + a[i][j];
	}
	for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)a[i][j] = S[i][j] + S[i + 1][j - 1] - S[i + 1][j] - S[i][j - 1];
	for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)if (a[i][j])Report(i, j);
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct - N = 5, K = 296, score = 10
2 Correct 2 ms 356 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 2 ms 432 KB Output is correct - N = 15, K = 22366, score = 10
4 Correct 2 ms 452 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 2 ms 452 KB Output is correct - N = 55, K = 4006396, score = 10
6 Correct 2 ms 576 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 2 ms 576 KB Output is correct - N = 77, K = 15385346, score = 10
8 Correct 2 ms 628 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 2 ms 676 KB Output is correct - N = 99, K = 42035827, score = 10
10 Correct 2 ms 804 KB Output is correct - N = 100, K = 43760000, score = 10