Submission #1220843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220843		mariamtsagareli	Square or Rectangle? (NOI19_squarerect)	C++20	18 / 100	0 ms	324 KiB

squarerect

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

extern bool inside_shape(int,int);

bool am_i_square(int n,int q){
    int c=(n+1)/2,s=(n+10)/11,px=c,py=c;
    for(int i=1;i<=10;i++){
        int t=i*s;
        if(t>n) t=n;
        if(inside_shape(c,t)){ px=c; py=t; break; }
    }
    int l=1,r=px,m;
    while(l<r){
        m=(l+r)/2;
        if(inside_shape(m,py)) r=m;
        else l=m+1;
    }
    int lft=l;
    l=px; r=n;
    while(l<r){
        m=(l+r+1)/2;
        if(inside_shape(m,py)) l=m;
        else r=m-1;
    }
    int rgt=l;
    int u=1,d=py;
    l=1; r=py;
    while(l<r){
        m=(l+r)/2;
        if(inside_shape(px,m)) r=m;
        else l=m+1;
    }
    int top=l;
    l=py; r=n;
    while(l<r){
        m=(l+r+1)/2;
        if(inside_shape(px,m)) l=m;
        else r=m-1;
    }
    int bot=l;
    return (rgt-lft)==(bot-top);
}

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