Submission #1213571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213571		exoworldgd	Square or Rectangle? (NOI19_squarerect)	C++20	0 / 100	0 ms	328 KiB

squarerect

#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 (int 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 (int 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 h=b-t+1,w=r-l+1;
    return w == h;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 19
• Subtask 3: 0 / 18
• Subtask 4: 0 / 49