Submission #317342

#	Time	Username	Problem	Language	Result	Execution time	Memory
317342		sebinkim	Square or Rectangle? (NOI19_squarerect)	C++14	100 / 100	1 ms	384 KiB

squarerect

#include "squarerect.h"
#include <bits/stdc++.h>

using namespace std;

bool am_i_square(int N, int Q)
{
	auto ask = [&](int x, int y){
		if(x < 1 || x > N || y < 1 || y > N) return false;
		else return inside_shape(x, y);
	};

	int i, j, a, b, c, d;

	a = b = N; c = d = 1;
	for(i = 20; i < 100; i += 20){
		for(j = 20; j < 100; j += 20){
			if(ask(i, j)){
				a = min(a, i); b = min(b, j);
				c = max(c, i); d = max(d, j);
			}
		}
	}
	if(a == N){
		for(i = 20; i <= 100; i += 20){
			if(ask(i, N)){ a = i; break; }
			if(ask(N, i)){ b = i; break; }
		}
		for(i = 16; i >= 1; i >>= 1){
			if(ask(a + i, b)) a += i;
			if(ask(a, b + i)) b += i;
		}
		return ask(a - 19, b - 19) && !ask(a - 19, b - 20)
			&& !ask(a - 20, b - 19) && !ask(a - 20, b - 20);
	}
	else{
		for(i = 16; i >= 1; i >>= 1){
			if(ask(a - i, b)) a -= i;
			if(ask(a, b - i)) b -= i;
			if(ask(c + i, b)) c += i;
		}
		return ask(a, c - a + b) && !ask(a, c - a + b + 1);
	}
}

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