Submission #53330

#	Time	Username	Problem	Language	Result	Execution time	Memory
53330		ics0503	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	100 / 100	2 ms	804 KiB

treasure

#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);
}

• Subtask 1: 100 / 100