#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);
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
