oj.uz

답안 #4546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4546 2013-10-24T13:51:15 Z tncks0121 보물 찾기 (CEOI13_treasure2) C++
100 / 100
 3 ms 2032 KB 
#include "treasure.h"
#include <stdio.h>
#include <memory.h>
#include <map>

using namespace std;

int A[105][105], B[105][105], C[105][105], D[105][105], R[105][105];
int S[105][105];
int N;
map<int, int> rec;

int get (int a, int b, int c, int d) {
    int x = (a-1)*N+b-1, y = (c-1)*N+d-1;  
    int z = x*N*N + y;
    if(!rec.count(z)) rec[z] = countTreasure(a, b, c, d);
    return rec[z];
}

void findTreasure (int N) {
    ::N = N;

    int i, j;
     
    int T = N/2+1;
     
    // 각 사분면에서 최선의 경우를 가져옴
    for(i = 1; i <= T; i++) {
        for(j = 1; j <= T; j++) A[i][j] = get(i, j, N, N);
        for(j = T; j <= N; j++) B[i][j] = get(i, 1, N, j);
    }
     
    for(i = T; i <= N; i++) {
        for(j = 1; j <= T; j++) C[i][j] = get(1, j, i, N);
        for(j = T; j <= N; j++) D[i][j] = get(1, 1, i, j);
    }
     
    // 그러면 r = T or c = T인 십자가 제외하고 모든 게 다 나옴
    for(i = T-1; i > 0; i--) {
        for(j = T-1; j > 0; j--) R[i][j] = A[i][j] - A[i][j+1] - A[i+1][j] + A[i+1][j+1];
        for(j = T+1; j <= N; j++) R[i][j] = B[i][j] - B[i][j-1] - B[i+1][j] + B[i+1][j-1];
    }
     
    for(i = T+1; i <= N; i++) {
        for(j = T-1; j > 0; j--) R[i][j] = C[i][j] - C[i][j+1] - C[i-1][j] + C[i-1][j+1];
        for(j = T+1; j <= N; j++) R[i][j] = D[i][j] - D[i][j-1] - D[i-1][j] + D[i-1][j-1];
    }
     
    // r = T, c > T인 십자가 처리
    memset(S, 0, sizeof S);
    for(i = 1; i < T; i++) for(j = T+1; j <= N; j++) S[i][j] = S[i-1][j] + R[i][j];
    for(j = N; j >= T+1; j--) R[T][j] = D[T][j] - D[T][j-1] - S[T-1][j];
     
    // 그럼 c > T인 경우는 다 처리가 끝났고 c <= T만 남았음
    // 이제 r < T, c = T인 경우 처리
    memset(S, 0, sizeof S);
    for(i = 1; i < T; i++) {
        R[i][T] = A[i][T] - A[i+1][T];
        for(j = T+1; j <= N; j++) R[i][T] -= R[i][j];
    }
     
    // r > T, c = T인 경우 처리. 위와 똑같이 해줄 수 있음
    memset(S, 0, sizeof S);
    for(i = T+1; i <= N; i++) {
        R[i][T] = C[i][T] - C[i-1][T];
        for(j = T+1; j <= N; j++) R[i][T] -= R[i][j];
    }
     
    // 이제 c < T인 경우만 남았음. r = T, c < T인 직선 처리
    memset(S, 0, sizeof S);
    for(i = N; i >= T; i--) for(j = N; j > 0; j--) S[i][j] = S[i+1][j] + S[i][j+1] - S[i+1][j+1] + R[i][j];
    for(j = T-1; j > 0; j--) R[T][j] = A[T][j] - A[T][j+1] - S[T+1][j] + S[T+1][j+1];
     
     
    // r = c = T 부분 (정가운데) 처리
    R[T][T] = A[T][T] + B[T][T] + C[T][T] + D[T][T] - A[1][1];
    for(i = 1; i <= N; i++) if(i != T) R[T][T] -= (R[i][T] + R[T][i]);
    R[T][T] /= 3;
    /*
    puts("");
    for(i = 1; i <= N; i++) {
        printf("%3d ", i);
        for(j = 1; j <= N; j++) {
            printf("%3d",R[i][j]);
        }
        puts("");
    }*/
     
    for(i = 1; i <= N; i++) {
        for(j = 1; j <= N; j++) {
            if(R[i][j] == 1) 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)");
                                  ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1504 KB Output is correct - N = 5, K = 289, score = 10
2 Correct 0 ms 1504 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 0 ms 1504 KB Output is correct - N = 15, K = 22289, score = 10
4 Correct 0 ms 1504 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 0 ms 1636 KB Output is correct - N = 55, K = 4005289, score = 10
6 Correct 0 ms 1768 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 0 ms 1768 KB Output is correct - N = 77, K = 15383161, score = 10
8 Correct 0 ms 1900 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 3 ms 2032 KB Output is correct - N = 99, K = 42032201, score = 10
10 Correct 3 ms 2032 KB Output is correct - N = 100, K = 43760000, score = 10