oj.uz

Submission #425467

# Submission time Handle Problem Language Result Execution time Memory
425467 2021-06-13T04:08:17 Z errorgorn Square or Rectangle? (NOI19_squarerect) C++17
100 / 100
 1 ms 204 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct