Submission #1193118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193118		loom	Square or Rectangle? (NOI19_squarerect)	C++20	100 / 100	1 ms	324 KiB

squarerect

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

bool am_i_square(int N, int Q){
	bool xy[101][101];
	for(int x=20; x<=80; x+=20){
		for(int y=20; y<=80; y+=20){
			xy[x][y] = inside_shape(x, y);
		}
	}

	for(int x=20; x<=80; x+=20){
		for(int y=20; y<=80; y+=20){
			if(xy[x][y]){
				//<<x<<" "<<y<<'\n';
				int right;
				for(int i=40; i<=100; i+=20){
					if(i == 100 or (!xy[x][i] and i > y)){
						int lo = i-20, hi = i;
						while(lo < hi){
							int mid = lo + (hi-lo+1)/2;

							if(inside_shape(x, mid)){
								lo = mid;
							}else hi = mid-1;
						}
						right = lo;
						//<<right<<'\n';
						break;
					}
				}

				int left;
				for(int i=60; i>=0; i-=20){
					if(i == 0 or (!xy[x][i] and i < y)){
						int lo = max(i,1), hi = i+20;
						while(lo < hi){
							int mid = lo + (hi-lo)/2;

							if(inside_shape(x, mid)){
								hi = mid;
							}else lo = mid+1;
						}
						left = lo;
						//<<left<<'\n';
						break;
					}
				}

				int bottom;
				for(int i=40; i<=100; i+=20){
					if(i == 100 or (!xy[i][y] and i > x)){
						int lo = i-20, hi = i;
						while(lo < hi){
							int mid = lo + (hi-lo+1)/2;

							if(inside_shape(mid, y)){
								lo = mid;
							}else hi = mid-1;
						}
						bottom = lo;
						//<<bottom<<'\n';
						break;
					}
				}

				int side = right - left + 1;
				int check = bottom - side + 1;

				if(check < 1) return false;
				if((check == 1 and inside_shape(check, y)) or (inside_shape(check, y) and !inside_shape(check-1, y))){
					return true;
				}
				return false;
			}
		}
	}

	for(int y=20; y<=100; y+=20){
		xy[100][y] = inside_shape(100, y);
	}
	for(int x=20; x<=80; x+=20){
		xy[x][100] = inside_shape(x, 100);
	}

	for(int y=20; y<=100; y+=20){
		if(xy[100][y]){
			//<<100<<" "<<y<<'\n';
			int right;
			for(int i=40; i<=100; i+=20){
				if(i == 100 or (!xy[100][i] and i > y)){
					int lo = i-20, hi = i;
					while(lo < hi){
						int mid = lo + (hi-lo+1)/2;

						if(inside_shape(100, mid)){
							lo = mid;
						}else hi = mid-1;
					}
					right = lo;
					//<<right<<'\n';
					break;
				}
			}

			int check = right - 20 + 1;
			if(((check == 1 and inside_shape(100, check)) or (inside_shape(100, check) and !inside_shape(100, check-1))) and inside_shape(81, check)){
				if(check == 81 and xy[80][100]) return false;
				return true;
			}
			return false;
		}
	}
	for(int x=20; x<=80; x+=20){
		if(xy[x][100]){
			int bottom;
			for(int i=40; i<=100; i+=20){
				if(i == 100 or (!xy[i][100] and i > x)){
					int lo = i-20, hi = i;
					while(lo < hi){
						int mid = lo + (hi-lo+1)/2;

						if(inside_shape(mid, 100)){
							lo = mid;
						}else hi = mid-1;
					}
					bottom = lo;
					//<<bottom<<'\n';
					break;
				}
			}

			int check = bottom - 20 + 1;
			if(((check == 1 and inside_shape(check, 100)) or (inside_shape(check, 100) and !inside_shape(check-1, 100))) and inside_shape(check, 81)){
				return true;
			}
			return false;
		}
	}
	return false;
}

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