제출 #310776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310776		Fischer	보물 찾기 (CEOI13_treasure2)	C++14	44 / 100	1 ms	384 KiB

treasure

#include <bits/stdc++.h>
#include "treasure.h"
using namespace std;

int query(int r1, int c1, int r2, int c2) {
    return countTreasure(r1, c1, r2, c2);
}

const int maxn = 110;
bool mat[maxn][maxn];
void f(int x1, int y1, int x2, int y2, int total) {
    if (x1 > x2 || y1 > y2) return;
    if (total == 0) return;
    if (total == (x2 - x1 + 1) * (y2 - y1 + 1)) {
        for (int r = x1; r <= x2; ++r) {
            for (int c = y1; c <= y2; ++c) {
                mat[r][c] = 1;
            }
        }
        return;
    }
    int mid1 = (x1 + x2) / 2;
    int mid2 = (y1 + y2) / 2;
    int t11 = query(x1, y1, mid1, mid2);
    int t12 = query(x1, y1, x2, mid2) - t11;
    int t21 = query(x1, y1, mid1, y2) - t11;
    f(x1, y1, mid1, mid2, t11);
    f(mid1+1, y1, x2, mid2, t12);
    f(x1, mid2+1, mid1, y2, t21);
    f(mid1+1, mid2+1, x2, y2, total - t11 - t12 - t21);
}

void findTreasure(int n) {
    int total = query(1, 1, n, n);
    f(1, 1, n, n, total);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (mat[i][j]) Report(i, j);
        }
    }
}

• Subtask 1: 44 / 100