Submission #1220847

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

squarerect

#include "squarerect.h"    // provided header
#include <cstdlib>         // for srand, rand

extern bool inside_shape(int,int);

bool am_i_square(int n,int q){
    if(q>50){
        int i=0,x=-1,y=-1;
        srand(74231);
        while(i<q/2){
            int a = rand()%n + 1;
            int b = rand()%n + 1;
            if(inside_shape(a,b)){ x=a; y=b; break; }
            i++;
        }
        if(x<0){
            for(int a=1; a<=n && i<q/2; a+=5)
                for(int b=1; b<=n && i<q/2; b+=5){
                    if(inside_shape(a,b)){ x=a; y=b; break; }
                    i++;
                }
        }
        if(x<0) x = y = 1;
        int l=x,r=x,u=y,d=y;
        while(i<q && l>1){
            if(inside_shape(l-1,y)) l--; else break;
            i++;
        }
        while(i<q && r<n){
            if(inside_shape(r+1,y)) r++; else break;
            i++;
        }
        while(i<q && u>1){
            if(inside_shape(x,u-1)) u--; else break;
            i++;
        }
        while(i<q && d<n){
            if(inside_shape(x,d+1)) d++; else break;
            i++;
        }
        return (r-l)==(d-u);
    } else {
        int c=(n+1)/2, s=(n+10)/11, p=c, o=c;
        for(int i=1;i<=10;i++){
            int t = i*s;
            if(t>n) t = n;
            if(inside_shape(c,t)){ p=c; o=t; break; }
        }
        int l=1, r=p, m;
        while(l<r){
            m=(l+r)/2;
            if(inside_shape(m,o)) r=m; else l=m+1;
        }
        int f=l;
        l=p; r=n;
        while(l<r){
            m=(l+r+1)/2;
            if(inside_shape(m,o)) l=m; else r=m-1;
        }
        int g=l;
        int u=1, d=o;
        l=1; r=o;
        while(l<r){
            m=(l+r)/2;
            if(inside_shape(p,m)) r=m; else l=m+1;
        }
        int h=l;
        l=o; r=n;
        while(l<r){
            m=(l+r+1)/2;
            if(inside_shape(p,m)) l=m; else r=m-1;
        }
        int k=l;
        return (g-f)==(k-h);
    }
}

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