Submission #1220842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220842		mariamtsagareli	Square or Rectangle? (NOI19_squarerect)	C++20	33 / 100	1 ms	328 KiB

squarerect

#include <bits/stdc++.h>
using namespace std;

extern bool inside_shape(int,int);

bool am_i_square(int n,int q){
    int m=(n+7)/8,x=1,y=1;
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            int a=min(1+i*m,n),b=min(1+j*m,n);
            if(inside_shape(a,b)){ x=a; y=b; i=8; break; }
        }
    }
    int l=1,h=x;
    while(l<h){
        int m2=(l+h)/2;
        if(inside_shape(m2,y)) h=m2;
        else l=m2+1;
    }
    int r=x,l2=x;
    h=n;
    while(l2<h){
        int m2=(l2+h+1)/2;
        if(inside_shape(m2,y)) l2=m2;
        else h=m2-1;
    }
    r=l2;
    int u=1,h2=y;
    while(u<h2){
        int m2=(u+h2)/2;
        if(inside_shape(x,m2)) h2=m2;
        else u=m2+1;
    }
    int d=y,u2=y;
    h2=n;
    while(u2<h2){
        int m2=(u2+h2+1)/2;
        if(inside_shape(x,m2)) u2=m2;
        else h2=m2-1;
    }
    d=u2;
    return (r-l)==(d-u);
}

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