#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
int nn;
const int NN = 105;
int disc[NN][NN];
map<pair<pii, pii>, int> vl;
int go(int i1, int j1, int i2, int j2){
if(i1 == 0 || j1 == 0 || i2 > nn || j2 > nn || i2 == 0 || j2 == 0 || i1 > nn || j2 > nn || i1 > i2 || j1 > j2)
return 0;
if(vl.count(mp(mp(i1,j1), mp(i2,j2))))
return vl[mp(mp(i1,j1), mp(i2,j2))];
int ans = 0;
for(int i = i1; i <= i2; i ++ ){
for(int j = j1; j <= j2; j ++ ){
if(disc[i][j] == -1){
ans = -1;
break;
}
ans += disc[i][j];
}
if(ans == -1)
break;
}
if(ans == -1){
int cnt = countTreasure(i1,j1,i2,j2);
vl[mp(mp(i1,j1), mp(i2,j2))]=cnt;
if(cnt == 0){
for(int i = i1; i <= i2; i ++ ){
for(int j = j1; j <= j2; j ++ ){
disc[i][j] = 0;
}
}
}
else if(cnt == (i2-i1+1) * (j2-j1+1)){
for(int i = i1; i <= i2; i ++ ){
for(int j = j1; j <= j2; j ++ ){
disc[i][j] = 1;
}
}
}
return cnt;
}
else
return ans;
}
void findTreasure (int n) {
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= n ; j ++ ){
disc[i][j]=-1;
}
}
nn = n;
int l1 = 0, l2 = 0, l3 = 0, l4 = 0;
int lef, rig;
int up, dow;
int cnt;
vector<pii> shit;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= n; j ++ ){
if(disc[i][j] == -1){
lef = j;
rig = n-j+1;
up = i;
dow = n-i+1;
l1 = lef*up+(lef-1)*up+lef*(up-1)+(lef-1)*(up-1);
l2 = rig*up+(rig-1)*up+rig*(up-1)+(rig-1)*(up-1);
l3 = lef*dow+(lef-1)*dow+lef*(dow-1)+(lef-1)*(dow-1);
l4 = rig*dow+(rig-1)*dow+rig*(dow-1)+(rig-1)*(dow-1);
if(l1 >= l2 && l1 >= l3 && l1 >= l4){
cnt = go(1, 1, i, j) - go(1, 1, i - 1, j) - go(1, 1, i, j - 1) + go(1, 1, i - 1, j - 1);
if(cnt){
disc[i][j]=1;
shit.push_back(mp(i,j));
}
}
else if(l2 >= l1 && l2 >= l3 && l2 >= l4){
cnt = go(1, j, i, n) - go(1, j + 1, i, n) - go(1, j, i - 1, n) + go(1, j + 1, i - 1, n);
if(cnt){
disc[i][j]=1;
shit.push_back(mp(i,j));
}
}
else if(l3 >= l1 && l3 >= l2 && l3 >= l4){
cnt = go(i, 1, n, j) - go(i + 1, 1, n, j) - go(i, 1, n, j - 1) + go(i + 1, 1, n, j - 1);
if(cnt){
disc[i][j]=1;
shit.push_back(mp(i, j));
}
}
else{
cnt = go(i, j, n, n) - go(i + 1, j, n, n) - go(i, j + 1, n, n) + go(i + 1, j + 1, n, n);
if(cnt){
disc[i][j]=1;
shit.push_back(mp(i, j));
}
}
}
}
}
for(auto p : shit)
Report(p.fi, p.se);
}
