#include "squarerect.h"
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
struct BinarySearch
{
using F = function<bool(int)>;
F pred;
BinarySearch(F f) : pred(f) {}
int lower_bound(int min_v, int max_v, bool flipped = false)
{
int res_v = max_v + 1;
while (min_v <= max_v)
{
int mid_v = (min_v + max_v) >> 1;
if (pred(mid_v) ^ flipped)
res_v = mid_v, max_v = mid_v - 1;
else
min_v = mid_v + 1;
}
return res_v;
}
int upper_bound(int min_v, int max_v, bool flipped = false)
{
int res_v = min_v - 1;
while (min_v <= max_v)
{
int mid_v = (min_v + max_v) >> 1;
if (pred(mid_v) ^ flipped)
res_v = mid_v, min_v = mid_v + 1;
else
max_v = mid_v - 1;
}
return res_v;
}
};
const int MAX = 100 + 2;
struct Problem
{
int memo[MAX][MAX];
int N, Q, DIVIDERS, BLOCK_LEN;
Problem(int n = 1, int q = 1, int DIVIDERS = 1) : N(n), Q(q), DIVIDERS(DIVIDERS)
{
BLOCK_LEN = N / DIVIDERS;
memset(memo, -1, sizeof memo);
}
inline bool inside_shape_safe(int x, int y)
{
if (memo[x][y] == -1)
memo[x][y] = inside_shape(x, y);
return memo[x][y];
}
inline pair<int, int> master_grid(int i, int j)
{
return make_pair(i * BLOCK_LEN + 1, j * BLOCK_LEN + 1);
}
bool solve_large_from_cell(int x, int y)
{
BinarySearch bs_by_x([&](int t)
{ return inside_shape_safe(t, y); });
BinarySearch bs_by_y([&](int t)
{ return inside_shape_safe(x, t); });
int left = bs_by_x.lower_bound(1, x - 1);
int right = bs_by_x.lower_bound(x + 1, N, true);
int top = bs_by_y.lower_bound(1, y - 1);
int bottom = bs_by_y.lower_bound(y + 1, N, true);
return right - left == bottom - top;
}
bool solve_small_from_cell(int x, int y)
{
BinarySearch bs_by_x([&](int t)
{ return inside_shape_safe(t, y); });
BinarySearch bs_by_y([&](int t)
{ return inside_shape_safe(x, t); });
// BinarySearch bs_pad_x([&](int pad)
// { return inside_shape_safe(x - BLOCK_LEN + pad, y) and inside_shape_safe(x + BLOCK_LEN - pad, y); });
// BinarySearch bs_pad_y([&](int pad)
// { return inside_shape_safe(x, y - BLOCK_LEN + pad) and inside_shape_safe(x, y + BLOCK_LEN - pad); });
// int pad_x = bs_pad_x.lower_bound(1, BLOCK_LEN / 2);
// int pad_y = bs_pad_y.lower_bound(1, BLOCK_LEN / 2);
// int left, right, top, bottom;
// if (inside_shape_safe(x - BLOCK_LEN + pad_x, y)) {
// left = bs_by_x.lower_bound();
// }
int left = bs_by_x.lower_bound(max(1, x - BLOCK_LEN + 1), x - 1);
int top = bs_by_y.lower_bound(max(1, y - BLOCK_LEN + 1), y - 1);
int right = bs_by_x.lower_bound(max(x + 1, left + BLOCK_LEN), min(N, x + BLOCK_LEN - 1), true);
int bottom = bs_by_y.lower_bound(max(y + 1, top + BLOCK_LEN), min(N, y + BLOCK_LEN - 1), true);
return right - left == bottom - top;
// return false;
}
};
bool am_i_square(int N, int Q)
{
Problem problem(N, Q, 5);
mt19937 rng;
vector<pair<int, int>> odd_cells, even_cells;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
if ((i + j) % 2 == 1)
{
int x, y;
tie(x, y) = problem.master_grid(i, j);
odd_cells.emplace_back(x, y);
}
shuffle(odd_cells.begin(), odd_cells.end(), rng);
for (const auto &e : odd_cells)
{
int x, y;
tie(x, y) = e;
if (inside_shape(x, y))
return problem.solve_large_from_cell(x, y);
}
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
if ((i + j) % 2 == 0)
{
int x, y;
tie(x, y) = problem.master_grid(i, j);
even_cells.emplace_back(x, y);
}
shuffle(even_cells.begin(), even_cells.end(), rng);
for (const auto &e : even_cells)
{
int x, y;
tie(x, y) = e;
if (inside_shape(x, y))
return problem.solve_small_from_cell(x, y);
}
return false;
}
