| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 94886 | emphasis10 | Treasure (different grader from official contest) (CEOI13_treasure2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
typedef long long ll;
static int N;
static char A[105][105];
static int S[105][105];
static char Chk[105][105];
static ll K;
static int treasure_cells;
void my_assert(int a, const char* s) {
if (!a) {
puts(s);
exit(0);
}
}
int countTreasure(int r1, int c1, int r2, int c2) {
if (!(1 <= r1 && r1 <= r2 && r2 <= N && 1 <= c1 && c1 <= c2 && c2 <= N)) {
printf("check the range of the parameters of countTreasure() : r1 = %d, c1 = %d, r2 = %d, c2 = %d", r1, c1, r2, c2);
exit(0);
}
my_assert(treasure_cells == 0, "you cannot call countTreasure() after calling Report()");
K += 1 + N * N - (r2 - r1 + 1) * (c2 - c1 + 1);
return S[r2][c2] - S[r2][c1 - 1] - S[r1 - 1][c2] + S[r1 - 1][c1 - 1];
}
void Report(int r, int c) {
if (!(1 <= r && r <= N && 1 <= c && c <= N)) {
printf("check the range of the parameters of Report() : r = %d, c = %d", r, c);
exit(0);
}
if (A[r][c] != 1) {
printf("no treasure at (r, c) : r = %d, c = %d", r, c);
exit(0);
}
if (Chk[r][c]) {
printf("already reported (r, c) : r = %d, c = %d", r, c);
exit(0);
}
++treasure_cells;
Chk[r][c] = 1;
}
int tmap[101][101]; //-1 : unknown 0 : no treasure 1: treasure
int dir[2][4] = { {0,0,-1,1}, {1, -1, 0,0} };
int myN;
int totaltreasure;
void ecofind(int x1, int y1, int x2, int y2) {
if (totaltreasure == 0) return;
if (x1 == x2 && y1 == y2) {
for (int i = 0; i < 4; i++) {
int nx = x1 + dir[0][i];
int ny = y1 + dir[1][i];
if (nx >= 1 && nx <= myN && ny >= 1 && ny <= myN) {
if (tmap[nx][ny] == 1) {
int a, b, c, d;
if (x1 < nx) { a = x1, c = nx; }
else { a = nx, c = x1; }
if (y1 < ny) { b = y1, d = ny; }
else { b = ny, d = y1; }
tmap[x1][y1] = countTreasure(a, b, c, d) - 1;
if (tmap[x1][x2] == 1) --totaltreasure;
return;
}
}
}
tmap[x1][y1] = countTreasure(x1, y1, x2, y2);
if (tmap[x1][x2] == 1) --totaltreasure;
return;
}
int cnt = countTreasure(x1, y1, x2, y2);
if (cnt == 0) return;
if (cnt == (x2 - x1 + 1)*(y2 - y1 + 1)) {
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) tmap[i][j] = 1;
}
totaltreasure -= (x2 - x1 + 1)*(y2 - y1 + 1);
}
else {
int mid = (x1 + x2) / 2;
ecofind(x1, y1, mid, mid);
ecofind(mid + 1, y1, x2, mid);
ecofind(x1, mid + 1, mid, y2);
ecofind(mid + 1, mid + 1, x2, y2);
}
}
void findTreasure(int N) {
for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) tmap[i][j] = -1;
myN = N;
totaltreasure = countTreasure(1, 1, N, N);
if (totaltreasure == 0) return;
if (N == 1) {
if (countTreasure(1, 1, 1, 1) == 1) Report(1, 1);
return;
}
if (N % 2 == 0) {
int mid = (1 + N) / 2;
ecofind(1, 1, mid, mid);
ecofind(mid + 1, 1, N, mid);
ecofind(1, mid + 1, mid, N);
ecofind(mid + 1, mid + 1, N, N);
}
else {
int mid = N / 2;
ecofind(1, 1, mid, mid);
ecofind(mid + 1, 1, N-1, mid);
ecofind(1, mid + 1, mid, N - 1);
ecofind(mid + 1, mid + 1, N - 1, N - 1);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (tmap[i][j] == -1) tmap[i][j] = countTreasure(i, j, i, j);
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (tmap[i][j] == 1) Report(i, j);
}
}
}
int main() {
int i, j;
my_assert(scanf("%d", &N) == 1, "the first line of the input must be an integer N (1 <= N <= 100)");
my_assert(1 <= N && N <= 100, "check the range of N : 1 <= N <= 100");
for (i = 1; i <= N; i++) {
my_assert(scanf("%s", A[i] + 1) == 1, "the second~(N+1)th line must contain a N x N sized map");
my_assert(strlen(A[i] + 1) == N, "each line of the map must contain N zeroes or ones (before loop)");
for (j = 1; j <= N; j++) {
my_assert(A[i][j] == '0' || A[i][j] == '1', "each line of the map must contain N zeroes or ones (in loop)");
A[i][j] -= '0';
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
}
}
findTreasure(N);
my_assert(treasure_cells == S[N][N], "not all of the treasure cells have been reported");
printf("Successful : N = %d, K = %lld\n", N, K);
int score = 0;
if (K <= 7. / 16. * N*N*N*N + N * N) score = 10;
else if (K <= 7. / 16. * N*N*N*N + 2 * N*N*N) score = 8;
else if (K <= 3. / 4. * N*N*N*N) score = 4;
else if (K <= (ll)N*N*N*N) score = 1;
printf("score = %d\n", score);
return 0;
}