Submission #425467

#	Time	Username	Problem	Language	Result	Execution time	Memory
425467		errorgorn	Square or Rectangle? (NOI19_squarerect)	C++17	100 / 100	1 ms	204 KiB

squarerect

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

bool inside_shape(int X,int Y);

bool inside(int i,int j){
	if (i>100 || j>100) return false;
	else return inside_shape(i,j);
}

bool test1(int i,int j){
	int x1,x2,y1,y2;
	
	int hi,lo,mid;
	
	lo=i-20,hi=i;
	while (hi-lo>1){
		mid=(hi+lo)>>1;
		if (inside(mid,j)) hi=mid;
		else lo=mid;
	}
	x1=hi;
	
	lo=j-20,hi=j;
	while (hi-lo>1){
		mid=(hi+lo)>>1;
		if (inside(i,mid)) hi=mid;
		else lo=mid;
	}
	y1=hi;
	
	if (i<j){
		lo=j,hi=101;
		while (hi-lo>1){
			mid=(hi+lo)>>1;
			if (inside(i,mid)) lo=mid;
			else hi=mid;
		}
		y2=lo;
		
		//printf("%d %d ?? %d",x1,y1,y2);
		
		x2=x1+(y2-y1);
		return inside(x2,j) && !inside(x2+1,j);
	}
	else{
		lo=i,hi=101;
		while (hi-lo>1){
			mid=(hi+lo)>>1;
			if (inside(mid,j)) lo=mid;
			else hi=mid;
		}
		x2=lo;
		
		//printf("%d %d %d ??",x1,y1,x2);
		
		y2=y1+(x2-x1);
		return inside(i,y2) && !inside(i,y2+1);
	}
}


bool test2(int i,int j){
	int x1,x2,y1,y2;
	
	int lo,hi,mid;
	if (i==100){
		if (!inside(81,j)) return false;
		x1=81,x2=100;
		
		lo=j-20,hi=j;
		while (hi-lo>1){
			mid=(hi+lo)>>1;
			if (inside(i,mid)) hi=mid;
			else lo=mid;
		}
		y1=hi;
		
		y2=y1+(x2-x1);
		return inside(i,y2) && !inside(i,y2+1);
	}
	else{
		if (!inside(i,81)) return false;
		y1=81,y2=100;
		
		lo=i-20,hi=i;
		while (hi-lo>1){
			mid=(hi+lo)>>1;
			if (inside(mid,j)) hi=mid;
			else lo=mid;
		}
		x1=hi;
		
		x2=x1+(y2-y1);
		return inside(x2,j) && !inside(x2+1,j);
	}
}

bool am_i_square(int N, int Q) {
	if (inside_shape(20,20)) return test1(20,20);
	
	else if (inside_shape(40,20)) return test1(40,20);
	else if (inside_shape(20,40)) return test1(20,40);
	else if (inside_shape(40,40)) return test1(40,40);
	
	else if (inside_shape(60,20)) return test1(60,20);
	else if (inside_shape(60,40)) return test1(60,40);
	else if (inside_shape(20,60)) return test1(20,60);
	else if (inside_shape(40,60)) return test1(40,60);
	else if (inside_shape(60,60)) return test1(60,60);
	
	else if (inside_shape(80,20)) return test1(80,20);
	else if (inside_shape(80,40)) return test1(80,40);
	else if (inside_shape(80,60)) return test1(80,60);
	else if (inside_shape(20,80)) return test1(20,80);
	else if (inside_shape(40,80)) return test1(40,80);
	else if (inside_shape(60,80)) return test1(60,80);
	else if (inside_shape(80,80)) return test1(80,80);
	
	else if (inside_shape(100,20)) return test2(100,20);
	else if (inside_shape(20,100)) return test2(20,100);
	else if (inside_shape(100,40)) return test2(100,40);
	else if (inside_shape(40,100)) return test2(40,100);
	else if (inside_shape(100,60)) return test2(100,60);
	else if (inside_shape(60,100)) return test2(60,100);
	else if (inside_shape(100,80)) return test2(100,80);
	else if (inside_shape(80,100)) return test2(80,100);
	
	else if (inside_shape(100,100)) return true;
	
	return false;
}

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