| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1218986 | takoshanava | Square or Rectangle? (NOI19_squarerect) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "squarerect.h"
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
bool am_i_square(int N, int Q) {
int used = 0;
int mn = (N * N + 24) / 25;
int ms = (int)ceil(sqrt(mn));
int x = N, y = N;
bool found = false;
for (int i = ms; i <= N and !found; i += ms) {
for (int j = ms; j < i and !found; j += ms) {
if (used++, inside_shape(i, j)) {
x = i; y = j;
found = true;
break;
}
if (used++, inside_shape(j, i)) {
x = j; y = i;
found = true;
break;
}
}
if (found) break;
if (N < i + ms) break;
if (used++, inside_shape(i, i)) {
x = i; y = i;
found = true;
break;
}
}
int l = x - ms + 1, r = min(x, N - ms + 2);
while (l < r) {
int mid = l + (r - l) / 2;
if (used++, inside_shape(mid, y)) r = mid;
else l = mid + 1;
}
x = l;
if (N < x + ms - 1) return false;
l = y - ms + 1, r = min(y, N - ms + 2);
while (l < r) {
int mid = l + (r - l) / 2;
if (used++, inside_shape(x, mid)) r = mid;
else l = mid + 1;
}
y = l;
if (N < y + ms - 1) return false;
l = ms - 1;
r = min(N - x, N - y) + 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (used++, !inside_shape(x + mid, y + mid)) r = mid;
else l = mid + 1;
}
int side = l;
bool valid = side != ms - 1;
if (valid and x + side - 1 <= N and y + side <= N)
valid &= !inside_shape(x + side - 1, y + side);
if (valid and x + side <= N and y + side - 1 <= N)
valid &= !inside_shape(x + side, y + side - 1);
return valid;
}