제출 #59084

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

treasure

// 15.07

#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 pre[maxn][maxn];
int arr[maxn][maxn];
int n;

void calc_square1(int r1, int c1, int r2, int c2){
//	cout << r1 << "  " << c1 << "  " << r2 << "  "<< c2 << endl;
	for(int i = r1; i <= r2 + 1; i++){
		for(int j = c1; j <= c2 + 1; j++){
			pre[i][j] = countTreasure(i, j, n, n);
		}
	}

	for(int i = r1; i <= r2; i++){
		for(int j = c1; j <= c2; j++)
			arr[i][j] = pre[i][j] - pre[i + 1][j] - pre[i][j + 1] + pre[i + 1][j + 1]; 
	}
}

void calc_square2(int r1, int c1, int r2, int c2){
	for(int i = r1; i <= r2 + 1; i++){
		for(int j = c1 - 1; j <= c2; j++){
			pre[i][j] = countTreasure(i, 1, n, j);
		}
	}

	for(int i = r1; i <= r2; i++){
		for(int j = c1; j <= c2; j++)
			arr[i][j] = pre[i][j] - pre[i + 1][j] - pre[i][j - 1] + pre[i + 1][j - 1]; 
	}
}

void calc_square3(int r1, int c1, int r2, int c2){
	for(int i = r1 - 1; i <= r2; i++){
		for(int j = c1; j <= c2 + 1; j++){
			pre[i][j] = countTreasure(1, j, i, n);
		}
	}

	for(int i = r1; i <= r2; i++){
		for(int j = c1; j <= c2; j++)
			arr[i][j] = pre[i][j] - pre[i - 1][j] - pre[i][j + 1] + pre[i - 1][j + 1]; 
	}
}

void calc_square4(int r1, int c1, int r2, int c2){
	for(int i = r1 - 1; i <= r2; i++){
		for(int j = c1 - 1; j <= c2; j++){
			pre[i][j] = countTreasure(1, 1, i, j);
		}
	}

	for(int i = r1; i <= r2; i++){
		for(int j = c1; j <= c2; j++)
			arr[i][j] = pre[i][j] - pre[i - 1][j] - pre[i][j - 1] + pre[i - 1][j - 1]; 
	}
}


void findTreasure(int N){
	n = N;
	int mid = n / 2;
	calc_square1(1, 1, mid, mid);
	calc_square2(1, mid + 1, mid, n);

	calc_square3(mid + 1, 1, n, mid);
	calc_square4(mid + 1, mid + 1, n, n);


    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: 69 / 100