| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 91913 | easrui | 보물 찾기 (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;
}
void findTreasure(int N){
static int S[101][101]; // S[a][b] a행 b열까지합
int L,R,U,D,tmp,res;
int a;
if(a%2) a= N/2+1;
else a=(N+1)/2;
int b=(N+1)/2;
L=1,R=N,U=1,D=N;
int x = countTreasure(1,L,N,R);
tmp = x;
for(U=2,D=N;U<=a;U++){
res = countTreasure(U,L,D,R);
if(L==1){
S[U-1][R] = tmp - res;
}
else S[U-1][L-1] = S[U-1][N] - (tmp - res);
tmp = res;
}
tmp = x;
for(U=1,D=N-1;D>=b;D--){
res = countTreasure(U,L,D,R);
if(L==1) S[D+1][R] = tmp - res;
else S[D+1][L-1] = S[D+1][N] - (tmp - res);
tmp = res;
}
int t=0;
for(int i=1; i<=D; i++) t+=S[i][R];
if(L==1) S[D+1][R] = tmp - t;
else S[D+1][L-1] = S[D+1][N] - (tmp - t);
for(L=2,R=N;L<=a;L++){
int x = countTreasure(1,L,N,R);
tmp = x;
for(U=2,D=N;U<=a;U++){
res = countTreasure(U,L,D,R);
if(L==1) S[U-1][R] = tmp - res;
else S[U-1][L-1] = S[U-1][N] - (tmp - res);
tmp = res;
}
tmp = x;
for(U=1,D=N-1;D>=b;D--){
res = countTreasure(U,L,D,R);
if(L==1) S[D+1][R] = tmp - res;
else S[D+1][L-1] = S[D+1][N] - (tmp - res);
tmp = res;
}
int t=0;
for(int i=1; i<=D; i++) t+=S[i][R]-S[i][L-1];
if(L==1) S[D+1][R] = tmp - t;
else S[D+1][L-1] = S[D+1][N] - (tmp - t);
//printf("%d %d",D+1,L-1);
}
for(L=1,R=N-1;R>=b;R--){
int x = countTreasure(1,L,N,R);
tmp = x;
for(U=2,D=N;U<=a;U++){
res = countTreasure(U,L,D,R);
if(L==1) S[U-1][R] = tmp - res;
else S[U-1][L-1] = S[U-1][N] - (tmp - res);
tmp = res;
//int t=0;
//for(int i=1; i<=R-1; i++) t+=S[U-1][i];
//if(R-1<b) S[U-1][R-1] = S[U-1][R] - t;
}
tmp = x;
for(U=1,D=N-1;D>=b;D--){
res = countTreasure(U,L,D,R);
if(L==1){
S[D+1][R] = tmp - res;
//printf("%d %d %d\n",S[D+1][R],D+1,R);
}
else S[D+1][L-1] = S[D+1][N] - (tmp - res);
tmp = res;
//int t=0;
//for(int i=1; i<=R-1; i++) t+=S[D+1][i];
//if(R-1<b) S[D+1][R-1] = S[D+1][R] - t;
}
int t=0;
for(int i=1; i<=D; i++) t+=S[i][R];
if(L==1) S[D+1][R] = tmp - t;
else S[D+1][L-1] = S[D+1][N] - (tmp - t);
//printf("%d %d",D+1,R);
/*if(R-1<b){
t=0;
for(int i=1; i<=R-1 ;i++) t+=S[D+1][i];
printf("%d",S[D+1][2]);
S[D+1][R-1] = S[D+1][R]-t;
printf("%d %d\n",D+1,R-1);
}*/
}
//for(int i=1; i<=5; i++) printf("%d",S[3][i]);
for(int x=1; x<=N; x++)
for(int y=1; y<=N; y++){
if(S[y][x]!=S[y][x-1]){
Report(y,x);
}
}
}
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;
}