# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
519042 | thegrimbee | Square or Rectangle? (NOI19_squarerect) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
static int T;
static int N, Q, X1, X2, Y1, Y2, q;
bool inside_shape(int X, int Y) {
q++;
cout << X << ' ' << Y << '\n';
if (q > Q) {
printf("Wrong Answer. Used too many queries.\n");
exit(0);
}
if (X <= 0 || X > N || Y <= 0 || Y > N) {
printf("Wrong Answer. Query parameters out of range.\n");
exit(0);
}
return (X >= X1 && X <= X2 && Y >= Y1 && Y <= Y2);
}
bool am_i_square(int N, int Q) {
bool visited[100][100];
int i, j, tempi, tempj;
bool temp;
for (i = 1; i <100; i += 20){
for (j = 1; j < 100; j += 20){
if (inside_shape(i, j)){tempi = i; tempj = j;j=101;i=101;}
}
}
i = tempi;
j = tempj;
int lo, hi, mid, len, len2;
lo = j - 19;
hi = j;
mid = (lo + hi)/ 2;
if (lo > 0){
while (lo <= mid && !(tempi == lo && tempj == hi)){
tempi = lo;
tempj = hi;
temp = inside_shape(i, mid);
visited[i-1][mid-1] = temp;
if (temp)hi = mid;
else lo = mid;
mid = (lo + hi)/2;
}
}
else{
mid = j;
}
len = j - mid + (int)visited[i-1][mid-1];
lo = j + 19 - len;
hi = 101;
mid = (lo + hi)/2;
while (lo <= mid&& !(tempi == lo && tempj == hi)){
tempi = lo;
tempj = hi;
temp = inside_shape(i, mid);
visited[i-1][mid-1] = temp;
if (!temp)hi = mid;
else {lo = mid;if(mid - j + len > 101 - max(1, i - 20))return false;}
mid = (lo + hi)/2;
}
len += mid - j + (int)visited[i-1][mid-1] - 1;
if (len < 20)return false;
lo = max(1, i - 19);
hi = i;
mid = (lo + hi) / 2;
temp = false;
while (lo <= mid&& !(tempi == lo && tempj == hi)){
tempi = lo;
tempj = hi;
temp = inside_shape(mid, j);
visited[mid-1][j-1] = temp;
if (temp){hi = mid;if(101 - mid < len)return false;}
else lo = mid;
mid = (lo + hi)/2;
}
len2 = i - mid + (int)visited[mid-1][j-1];
temp = inside_shape(i + len-len2, j);
if (!temp) return false;
if (((i + len - len2 == 100) && temp) || (temp && !inside_shape(i + len-len2 + 1, j)))return true;
return false;
}
int main() {
if (scanf("%d%d%d", &T, &N, &Q) != 3) {
printf("Input file invalid.\n");
return 0;
}
int mxq = 0;
for (int i = 0; i < T; i++) {
if (scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2) != 4) {
printf("Input file invalid.\n");
return 0;
}
q = 0;
bool user_ans = am_i_square(N, Q);
bool act_ans = (Y2 - Y1) == (X2 - X1);
if (user_ans != act_ans) {
printf("Wrong Answer.\n");
exit(0);
}
mxq = max(mxq, q);
}
printf("Correct. Used %d out of %d queries.\n", mxq, Q);
}