#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define i64 int64_t
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << '\n';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define vt vector
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define fir first
#define sec second
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
// Total: 42 queries
bool am_i_square(int N, int Q) {
int n = N;
int r = 0, c = 0;
bool found = false;
// Phase 1: Find a cell inside the shape: 25 queries
for(int x=n/5; x<=n; x+=n/5) {
for(int y=n/5; y<=n; y+=n/5) {
bool res = inside_shape(x, y);
if(res) {
r = y, c = x;
found = true;
break;
}
}
if(found) break;
}
if(!found) return false;
// Phase 2: Binary search up to determine height : log(rc) = 11 queries
int h = 0, w = 0;
int high = max(1, r-n/5), low = r;
while(low < high) {
int m = (low + high + 1) >> 1;
if(inside_shape(r, m))
low = m;
else
high = m+1;
}
// show(low);
int high1 = n, low1 = r;
while(low1 < high1) {
int m = (low1 + high1 + 1) >> 1;
if(inside_shape(r, m))
low1 = m;
else
high1 = m-1;
}
// show(low1);
h = (low1 - low) + 1;
// Phase 3: Determine width: log2(n) = 4 queries
int left = max(1, c-n/5), right = c;
while(left < right) {
int m = (left + right) >> 1;
if(inside_shape(m, c))
right = m;
else
left = m+1;
}
// show(right);
if(c-right+1 > h) return false;
int p = c + h-(c-right+1);
// show(p);
if(p > n) return false;
// Last 2 queries
bool y1 = false, y2 = false;
if(p == n) y2 = false;
y1 = inside_shape(r, p);
if(p < n) y2 = inside_shape(r, p+1);
return (y1 && !y2 ? true : false);
}
