# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1213569 | exoworldgd | Square or Rectangle? (NOI19_squarerect) | C++20 | 0 ms | 0 KiB |
#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;
bool ask(int i, int j) {return inside_shape(i,j);}
bool am_i_square(int n, int q) {
int t=1,b=n,l=1,r=n,lo=1,hi=n;
while (lo < hi) {
int m = lo+(hi-lo)/2,yes=0;
for (i = 1; i<= n; i++) if (ask(m,i)) {yes=1; break;}
if (yes) hi = m;
else lo=m+1;
}
t=lo, lo= t, hi=n;
while (lo < hi) {
int m = lo+(hi-lo)/2,yes=0;
for (i = 1; i<= n; i++) if (ask(m,i)) {yes=1; break;}
if (yes) lo = m;
else hi=m-1;
}
b=lo;
lo = 1, hi = n;
while (lo < hi) {
int m = lo+(hi-lo)/2,yes=0;
for (int i = t; i <= b; i++) if (ask(i,m)) { yes = 1; break; }
if (yes) hi = m;
else lo = m+1;
}
l = lo, lo = l, hi=n;
while (lo < hi) {
int m = lo+(hi-lo)/2,yes=0;
for (int i = t; i <= b; i++) if (ask(i,m)) { yes = 1; break; }
if (yes) lo = m;
else hi = m-1;
}
r=lo;
int l=b-t+1,w=r-l+1;
return w == l;
}