#include "treasure.h"
#include <vector>
#include <map>
#include <utility>
#include <tuple>
using namespace std;
int n;
map<int, int> mp;
vector<int> line_total;
vector<vector<int>> grid_total;
int rect_to_hash(int y1, int x1, int y2, int x2){
int ret = y1-1;
ret *= n;
ret += x1-1;
ret *= n;
ret += y2-1;
ret *= n;
ret += x2-1;
return ret;
}
tuple<int, int, int, int> hash_to_rect(int hash){
int x2 = (hash % n) + 1;
hash /= n;
int y2 = (hash % n) + 1;
hash /= n;
int x1 = (hash % n) + 1;
hash /= n;
int y1 = (hash % n) + 1;
return make_tuple(y1, x1, y2, x2);
}
int get(int y1, int x1, int y2, int x2){
int hash = rect_to_hash(y1, x1, y2, x2);
if (mp.find(hash) == mp.end())
mp[hash] = countTreasure(y1, x1, y2, x2);
return mp[hash];
}
int getRectEnd(int endY, int startX){
if (endY == 0)
return 0;
if (n - endY > endY)
return get(1, startX, n, n) - get(endY+1, startX, n, n);
else
return get(1, startX, endY, n);
}
int getRectStart(int endY, int endX){
if (endY == 0)
return 0;
if (n - endY > endY)
return get(1, 1, n, endX) - get(endY+1, 1, n, endX);
else
return get(1, 1, endY, endX);
}
int getLine(int y){
return line_total[y] - line_total[y-1];
}
void calLine(){
line_total.assign(n+1, 0);
for (int i = 1; i <= n; i++){
line_total[i] = getRectEnd(i, 1);
}
}
int getGrid(int y, int x){
return grid_total[y][x] - grid_total[y][x-1];
}
void calGrid(){
grid_total.assign(n+1, vector<int>(n+1, 0));
for (int i = 1; i <= n; i++){
int left = 1;
int right = n-1;
while (right){
if (right > left){
grid_total[i][left] = getLine(i) - (getRectEnd(i, left+1) - getRectEnd(i-1, left+1));
}else{
grid_total[i][left] = getRectStart(i, left) - getRectStart(i-1, left);
}
left++;
right--;
}
grid_total[i][left] = getLine(i);
}
}
void findTreasure (int N) {
n = N;
mp.clear();
calLine();
calGrid();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (getGrid(i, j))
Report(i, j);
}
