| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1191133 | itslq | Square or Rectangle? (NOI19_squarerect) | C++20 | 0 ms | 0 KiB |
int searchRight(int x, int right, int y) {
int l = x + 1, r = right, m, ans = x;
while (l <= r) {
m = (l + r) >> 1;
if (inside_shape(m, y)) {
ans = m;
l = ++m;
} else r = --m;
}
return ans;
}
int searchLeft(int x, int left, int y) {
int l = left, r = x - 1, m, ans = x;
while (l <= r) {
m = (l + r) >> 1;
if (inside_shape(m, y)) {
ans = m;
r = --m;
} else l = ++m;
}
return ans;
}
int searchUp(int y, int up, int x) {
int l = y + 1, r = up, m, ans = y;
while (l <= r) {
m = (l + r) >> 1;
if (inside_shape(x, m)) {
ans = m;
l = ++m;
} else r = --m;
}
return ans;
}
bool am_i_square(int N, int Q) {
vector<vector<int>> qrys(4, vector<int>(4));
int mx = 100, my = 100, Mx = -1, My = -1;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (inside_shape(i * 20, j * 20)) {
mx = min(mx, i);
my = min(my, i);
Mx = max(Mx, i);
My = max(My, i);
}
}
}
if (Mx == -1) {
bool found = false;
for (int i = 1; i <= 5; i++) {
if (inside_shape(i * 20, 100)) {
if (found) return false;
found = true;
int lb = searchLeft(i * 20, max(1, i * 20 - 19), 100);
if (lb + 19 >= 100 ||
!inside_shape(lb + 19, 100) ||
(lb + 20 <= 100 && inside_shape(lb + 20, 100)) ||
!inside_shape(i * 20, 81) ||
inside_shape(i * 20, 80)
) return false;
}
}
for (int i = 1; i <= 4; i++) {
if (inside_shape(100, i * 20)) {
if (found) return false;
found = true;
int ub = searchUp(i * 20, i * 20 + 19, 100);
if (!inside_shape(100, ub - 19) ||
inside_shape(100, ub - 20) ||
!inside_shape(81, i * 20) ||
inside_shape(80, i * 20)
) return false;
}
}
return found;
} else {
int lb = searchLeft(mx * 20, max(1, mx * 20 - 19), my * 20);
int rb = searchRight(Mx * 20, Mx * 20 + 19, my * 20);
int ub = searchUp(My * 20, My * 20 + 19, My * 20);
int db = ub - rb + lb;
if (db < 1 ||
!inside_shape(mx * 20, db) ||
(db - 1 >= 1 && inside_shape(mx * 20, db - 1))
) return false;
return true;
}
}