oj.uz

Submission #872790

# Submission time Handle Problem Language Result Execution time Memory
872790 2023-11-13T19:33:29 Z rainboy Square or Rectangle? (NOI19_squarerect) C++17
100 / 100
 0 ms 352 KB 
#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.0 / 14.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
18.0 / 18.0

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

Subtask #4
49.0 / 49.0

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