#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int,int> quadra;
const int MAXN = 110;
static int matriz[MAXN][MAXN],N;
static map<quadra,int> previous_queries;
int doQuery(int x_i,int y_i,int x_f,int y_f){
if(x_i > x_f || y_i > y_f || min(x_i,x_f) == 0 || min(y_i,y_f) == 0 || max(x_i,x_f) > N || max(y_i,y_f) > N) return 0;
quadra davez = make_tuple(x_i,y_i,x_f,y_f);
if(previous_queries.count(davez)) return previous_queries[davez];
int qt = countTreasure(x_i, y_i, x_f, y_f);
previous_queries[davez] = qt;
return qt;
}
void findTreasure(int n){
previous_queries.clear();
memset(matriz,-1,sizeof(matriz));
N = n;
int mid = (1 + N)/2;
// Quarto inferior direito
for(int i = mid;i<=N;i++){
for(int j = mid;j<=N;j++){
if(matriz[i][j] != -1) continue;
matriz[i][j] = doQuery(1,1,i,j) - doQuery(1,1,i-1,j) - doQuery(1,1,i,j-1) + doQuery(1,1,i-1,j-1);
}
}
// Quarto inferior esquerdo
for(int i = mid;i<=N;i++){
for(int j = mid;j>=1;j--){
if(matriz[i][j] != -1) continue;
matriz[i][j] = doQuery(1,j,i,N) - doQuery(1,j,i-1,N) - doQuery(1,j+1,i,N) + doQuery(1,j+1,i-1,N);
}
}
// Quarto superior esquerdo
for(int i = mid;i>=1;i--){
for(int j = mid;j>=1;j--){
if(matriz[i][j] != -1) continue;
matriz[i][j] = doQuery(i,j,N,N) - doQuery(i+1,j,N,N) - doQuery(i,j+1,N,N) + doQuery(i+1,j+1,N,N);
}
}
// Quarto superior direito
for(int i = mid;i>=1;i--){
for(int j = mid;j<=N;j++){
if(matriz[i][j] != -1) continue;
matriz[i][j] = doQuery(i,1,N,j) - doQuery(i+1,1,N,j) - doQuery(i,1,N,j-1) + doQuery(i+1,1,N,j-1);
}
}
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
if(matriz[i][j] == 1) Report(i,j);
}
}
}
