Submission #1276943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276943		vibeduck	Square or Rectangle? (NOI19_squarerect)	C++20	18 / 100	1 ms	340 KiB

squarerect

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

bool debug = false;

bool am_i_square(int N, int Q) {
	int i = -1, j = -1;
	int k = (N + 4)/5;
	if(debug) cout << "K " << k << '\n';
	for (int a = k; a <= N; a += k) {
		for (int b = k; b <= N; b += k) {
			if (inside_shape(a, b)) {
				i = a; j = b;
				break;
			}
		}
		if (i != -1) break;
	}

	if(debug) cout << "i: " << i << '\n';
	if(debug) cout << "j: " << j << '\n';
	assert(i != -1);
	assert(j != -1);

	for (int b = 20; b >= 0; b--) {
		if (i + (1 << b) > N) continue;
		if (inside_shape(i + (1 << b), j)) i += (1 << b);
	}

	for (int b = 20; b >= 0; b--) {
		if (j + (1 << b) > N) continue;
		if (inside_shape(i, j + (1 << b))) j += (1 << b);
	}

	if(debug) cout << "bottomright:\n";
	if(debug) cout << "i: " << i << '\n';
	if(debug) cout << "j: " << j << '\n';

	for (int b = 20; b >= 0; b--) {
		if (min(i, j) - (1 << b) <= 0) continue;
		if (inside_shape(i - (1 << b), j - (1 << b))) {
			i -= (1 << b);
			j -= (1 << b);
		}
	}

	if(debug) cout << "toplefticouldfind:\n";
	if(debug) cout << "i: " << i << '\n';
	if(debug) cout << "j: " << j << '\n';

	int b1 = 0; if (i > 1) b1 = inside_shape(i - 1, j);
	int b2 = 0; if (j > 1) b2 = inside_shape(i, j - 1);

	if(debug) cout << b1 << " " << b2 << " are bools\n";

	assert(!(b1 && b2));

	return !(b1 ^ b2);
}

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