Submission #1219710

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

squarerect

#include <bits/stdc++.h>
using namespace std;
extern bool inside_shape(int x,int y);
bool am_i_square(int n,int q){
    if(q>50){
        int k=max(1,n/10),a,b,x,y,mid;
        for(a=1;a<=n;a+=k)for(b=1;b<=n;b+=k)if(inside_shape(a,b)){x=a;y=b;goto z;}
    z:;
        int l=1,r=x;
        while(l<r){mid=(l+r)/2;if(inside_shape(mid,y))r=mid;else l=mid+1;}
        int p=l;
        l=x;r=n;
        while(l<r){mid=(l+r+1)/2;if(inside_shape(mid,y))l=mid;else r=mid-1;}
        int s=l;
        int c=1,d=y;
        while(c<d){mid=(c+d)/2;if(inside_shape(x,mid))d=mid;else c=mid+1;}
        int t=c;
        c=y;d=n;
        while(c<d){mid=(c+d+1)/2;if(inside_shape(x,mid))c=mid;else d=mid-1;}
        int u=c;
        return (s-p)==(u-t);
    } else {
        int c=(n+1)/2,a=1,b=n,m;
        while(a<b){m=(a+b)/2;if(inside_shape(m,c))b=m;else a=m+1;}
        int p=a;
        a=1;b=n;
        while(a<b){m=(a+b+1)/2;if(inside_shape(m,c))a=m;else b=m-1;}
        int s=a;
        int e=1,f=n;
        while(e<f){m=(e+f)/2;if(inside_shape(c,m))f=m;else e=m+1;}
        int t=e;
        e=1;f=n;
        while(e<f){m=(e+f+1)/2;if(inside_shape(c,m))e=m;else f=m-1;}
        int u=e;
        return (s-p)==(u-t);
    }
}

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