#include "treasure.h"
int cnt;
int _map[105][105];
int n;
void init(int N) {
cnt = 0; n = N;
for (int i = 0; i <= N; i++)
for (int j = 0; j <= N; j++)
_map[i][j] = 0;
}
int score(int ly, int lx, int ry, int rx) {
int hap = 0;
hap = 1+ n*n - (ry - ly + 1)*(rx - lx + 1);
return hap;
}
int dnc(int ly, int lx, int ry, int rx, int t) {
if (ly == ry && lx == rx) {//한 칸 일때
if (t) {
_map[ly][lx] = 1;
return 1;
}
return 0;
}
int tmp = t;
int total = (ry - ly + 1)*(rx - lx + 1);
if (tmp == total) {
for (int i = ly; i <= ry; i++) {
for (int j = lx; j <= rx; j++) {
_map[i][j] = 1;
}
}
return tmp;
}
int midy = (ly + ry) / 2;
int midx = (lx + rx) / 2;
int now_cnt = 0;
int total_le = (ry - ly + 1)*(midx - lx + 1);
int h_le;
if (score(1, 1, ry, midx) + score(1, 1, ly, lx) + score(1, 1, ry, lx) + score(1, 1, ly, rx) >= score(ly, lx, ry, midx)) {
h_le = countTreasure(ly, lx, ry, midx);
}
else {
h_le = countTreasure(1, 1, ry, midx) - countTreasure(1, 1, ry, lx) - countTreasure(1, 1, ly, rx) + countTreasure(1, 1, ly, lx);
}
bool ok = true, ok1 = true;
if (h_le == total_le) {
ok = false;
for (int i = ly; i <= ry; i++) {
for (int j = lx; j <= midx; j++) {
_map[i][j] = 1;
}
}
now_cnt += total_le;
}
else if (tmp - h_le == total - total_le) {
ok1 = false;
for (int i = ly; i <= ry; i++) {
for (int j = midx + 1; j <= rx; j++) {
_map[i][j] = 1;
}
}
now_cnt += total - total_le;
}
int f;
if (score(1, 1, midy, midx) + score(1, 1, ly, lx) + score(1, 1, midy, lx) + score(1, 1, ly, midx) >= score(ly, lx, midy, midx)) {
f = countTreasure(ly, lx, midy, midx);
}
else {
f = countTreasure(1, 1, midy, midx) - countTreasure(1, 1, ly, lx) - countTreasure(1, 1, midy, lx) + countTreasure(1, 1, ly, midx);
}
if (ok && now_cnt < tmp)now_cnt += dnc(ly, lx, midy, midx, f);
if (ok1 && now_cnt < tmp)now_cnt += dnc(ly, midx + 1, midy, rx, countTreasure(ly, lx, midy, rx) - f);
if (ok && now_cnt < tmp)now_cnt += dnc(midy + 1, lx, ry, midx, h_le - f);
if (ok1 && now_cnt < tmp)now_cnt += dnc(midy + 1, midx + 1, ry, rx, tmp - now_cnt);
return now_cnt;
}
void findTreasure(int N) {
init(N);
//cnt = countTreasure(1, 1, N, N);
dnc(1, 1, N, N, countTreasure(1, 1, N, N));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (_map[i][j])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)");
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
248 KB |
Output is partially correct - N = 5, K = 513, score = 8 |
| 2 |
Partially correct |
1 ms |
356 KB |
Output is partially correct - N = 10, K = 8861, score = 1 |
| 3 |
Partially correct |
1 ms |
552 KB |
Output is partially correct - N = 15, K = 23056, score = 8 |
| 4 |
Incorrect |
1 ms |
552 KB |
Invalid Access |
| 5 |
Incorrect |
1 ms |
564 KB |
Invalid Access |
| 6 |
Incorrect |
1 ms |
564 KB |
Invalid Access |
| 7 |
Correct |
1 ms |
636 KB |
Output is correct - N = 77, K = 8262314, score = 10 |
| 8 |
Incorrect |
1 ms |
636 KB |
Error - not all of the treasure cells have been reported |
| 9 |
Incorrect |
2 ms |
636 KB |
Invalid Access |
| 10 |
Incorrect |
2 ms |
636 KB |
Invalid Access |
