제출 #59074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59074		zadrga	보물 찾기 (CEOI13_treasure2)	C++14	53 / 100	66 ms	700 KiB

treasure

// 13.12

#include "treasure.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 111

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

int arr[maxn][maxn];

void fill_arr(int r1, int c1, int r2, int c2, int val){
	for(int i = r1; i <= r2; i++){
		for(int j = c1; j <= c2; j++)
			arr[i][j] = val;
	}
}

int get(int r1, int c1, int r2, int c2){
	int ret = 0;
	for(int i = r1; i <= r2; i++){
		for(int j = c1; j <= c2; j++)
			ret += arr[i][j];
	}
	return ret;
}

int calc(int r1, int c1, int r2, int c2){
	if(r1 > r2 || c1 > c2)
		return -1;

	int ret = countTreasure(1, 1, r2, c2);
	ret -= get(1, 1, r2, c1 - 1);
	ret -= get(1, 1, r1 - 1, c2);
	ret += get(1, 1, r1 - 1, c1 - 1);
	return ret;
}


void solve(int r1, int c1, int r2, int c2, int val){
//	cout << r1 << "  " << c1 << "    " << r2 << "  " << c2 << ":   " << val << endl;

	if(r1 > r2 || c1 > c2)
		return;

	if(val == 0){
		fill_arr(r1, c1, r2, c2, 0);
		return;
	}

	if(val == (r2 - r1 + 1) * (c2 - c1 + 1)){
		fill_arr(r1, c1, r2, c2, 1);
		return;
	}

	int midr = (r1 + r2) / 2;
	int midc = (c1 + c2) / 2;

	int area1 = calc(r1, c1, midr, midc);
	solve(r1, c1, midr, midc, area1);

	int area2 = calc(r1, midc + 1, midr, c2);
	solve(r1, midc + 1, midr, c2, area2);

	int area3 = calc(midr + 1, c1, r2, midc);
	solve(midr + 1, c1, r2, midc, area3);

	int area4 = calc(midr + 1, midc + 1, r2, c2);
	solve(midr + 1, midc + 1, r2, c2, area4);
}




void findTreasure(int n){
	memset(arr, -1, sizeof(arr));

	int all = countTreasure(1, 1, n, n);
	solve(1, 1, n, n, all);

    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= n; j++){
    		if(arr[i][j] == 1) {
    //			cout << i << "  " << j << endl;
    			Report(i, j);
    		}
    	}
    }
}

• Subtask 1: 53 / 100