#include "treasure.h"
int cnt;
int _map[105][105];
void init(int n) {
cnt = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
_map[i][j] = 0;
}
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 = countTreasure(ly, lx, ry, midx);
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 = countTreasure(ly, lx, midy, 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 |
352 KB |
Output is partially correct - N = 10, K = 8927, score = 1 |
3 |
Partially correct |
2 ms |
424 KB |
Output is partially correct - N = 15, K = 23056, score = 8 |
4 |
Correct |
1 ms |
496 KB |
Output is correct - N = 16, K = 23523, score = 10 |
5 |
Partially correct |
2 ms |
640 KB |
Output is partially correct - N = 55, K = 8380159, score = 1 |
6 |
Partially correct |
2 ms |
640 KB |
Output is partially correct - N = 66, K = 16719720, score = 1 |
7 |
Correct |
2 ms |
640 KB |
Output is correct - N = 77, K = 8262314, score = 10 |
8 |
Correct |
2 ms |
640 KB |
Output is correct - N = 88, K = 10753869, score = 10 |
9 |
Partially correct |
2 ms |
640 KB |
Output is partially correct - N = 99, K = 92081510, score = 1 |
10 |
Partially correct |
2 ms |
640 KB |
Output is partially correct - N = 100, K = 96440934, score = 1 |