Submission #872790

#	Time	Username	Problem	Language	Result	Execution time	Memory
872790		rainboy	Square or Rectangle? (NOI19_squarerect)	C++17	100 / 100	0 ms	352 KiB

squarerect

#include "squarerect.h"

const int N = 100, M = 20;

using namespace std;

int solve(int i, int j) {
	if (inside_shape(i + 1, j + 1)) {
		int lower, upper, i1, j1, i2, j2;
		lower = -1, upper = i;
		while (upper - lower > 1) {
			i1 = (lower + upper) / 2;
			if (inside_shape(i1 + 1, j + 1))
				upper = i1;
			else
				lower = i1;
		}
		i1 = upper;
		lower = -1, upper = j;
		while (upper - lower > 1) {
			j1 = (lower + upper) / 2;
			if (inside_shape(i + 1, j1 + 1))
				upper = j1;
			else
				lower = j1;
		}
		j1 = upper;
		if (i == 0)
			return inside_shape(i + M, j1 + 1) && (j1 + M == N || !inside_shape(i + 1, j1 + M + 1)) ? 1 : 0;
		else if (j == 0)
			return inside_shape(i1 + 1, j + M) && (i1 + M == N || !inside_shape(i1 + M + 1, j + 1)) ? 1 : 0;
		else {
			lower = i, upper = i + M;
			while (upper - lower > 1) {
				i2 = (lower + upper) / 2;
				if (inside_shape(i2 + 1, j + 1))
					lower = i2;
				else
					upper = i2;
			}
			i2 = lower, j2 = j1 + i2 - i1;
			return j2 < N && inside_shape(i + 1, j2 + 1) && (j2 + 1 == N || !inside_shape(i + 1, j2 + 2)) ? 1 : 0;
		}
	}
	return -1;
}

bool am_i_square(int n, int q) {
	for (int i = N - M; i >= 0; i -= M)
		for (int j = N - M; j >= i; j -= M) {
			int x;
			if ((x = solve(i, j)) != -1)
				return x == 0 ? false : true;
			if (j != i && (x = solve(j, i)) != -1)
				return x == 0 ? false : true;
		}
	return false;
}

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