#include "squarerect.h" #include <bits/stdc++.h> 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_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); 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(max(1, x - BLOCK_LEN + 1), x - 1); int right = bs_by_x.lower_bound(x + 1, min(N, x + BLOCK_LEN - 1), true); int top = bs_by_y.lower_bound(max(1, y - BLOCK_LEN + 1), y - 1); int bottom = bs_by_y.lower_bound(y + 1, 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); 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); 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); if (inside_shape(x, y)) return problem.solve_small_from_cell(x, y); // return problem.solve_large_from_cell(x, y); } return false; }