#include "treasure.h"
#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;
typedef tuple<int,int,int,int> quadra;
const int MAXN = 110;
static int matriz[MAXN][MAXN],N,bit[MAXN][MAXN];
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;
}
static void update(int x,int y,int delta){
for(int i = x;i<=N;i += LSOne(i)){
for(int j = y;j<=N;j += LSOne(j)){
bit[i][j] += delta;
}
}
}
static int read(int x,int y){
int ans = 0;
for(int i = x;i>0;i -= LSOne(i)){
for(int j = y;j > 0;j -= LSOne(j)){
ans += bit[i][j];
}
}
return ans;
}
static int query2d(int x_i,int y_i,int x_f,int y_f){
if(x_i > x_f || y_i > y_f) return 0;
return read(x_f,y_f) - read(x_i-1,y_f) - read(x_f,y_i-1) + read(x_i-1,y_i-1);
}
void solve(int x,int left,int right,int cnt){
if(cnt == 0){
for(int i = left;i<=right;i++){
matriz[x][i] = 0;
}
return;
}
if(right - left + 1 == cnt){
for(int i = left;i<=right;i++){
if(matriz[x][i] != -1) continue;
matriz[x][i] = 1;
update(x,i,1);
}
return;
}
int mid = (left+right)/2;
int qt = doQuery(1,1,x,mid) - query2d(1,1,x,left - 1) - query2d(1,left,x-1,mid);
solve(x,left,mid,qt);
solve(x,mid+1,right,cnt - qt);
}
void findTreasure(int n){
previous_queries.clear();
memset(matriz,-1,sizeof(matriz));
memset(bit,0,sizeof(bit));
N = n;
int mid = (1 + N)/2;
// 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);
}
}
// Constroi BIT 2d
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
if(matriz[i][j] != -1){
update(i,j,matriz[i][j]);
}
}
}
// Quarto inferior direito
for(int i = mid+1;i<=N;i++){
int qt = doQuery(1,1,i,N) - query2d(1,1,i,mid) - query2d(1,mid+1,i-1,N);
solve(i,mid+1,N,qt);
}
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
if(matriz[i][j] == 1) Report(i,j);
}
}
}
