Submission #1191140

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

squarerect

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

map<int, bool> memo;

bool query(int X, int Y) {
    const int v = X * 200 + Y;
    if (memo.find(v) != memo.end()) return memo[v];
    return memo[v] = inside_shape(X, Y);
}

int searchRight(int x, int right, int y) {
	int l = x + 1, r = right, m, ans = x;
	while (l <= r) {
		m = (l + r) >> 1;
		if (query(m, y)) {
			ans = m;
			l = ++m;
		} else r = --m;
	}
	return ans;
}

int searchLeft(int x, int left, int y) {
	int l = left, r = x - 1, m, ans = x;
	while (l <= r) {
		m = (l + r) >> 1;
		if (query(m, y)) {
			ans = m;
			r = --m;
		} else l = ++m;
	}
	return ans;
}

int searchUp(int y, int up, int x) {
	int l = y + 1, r = up, m, ans = y;
	while (l <= r) {
		m = (l + r) >> 1;
		if (query(x, m)) {
			ans = m;
			l = ++m;
		} else r = --m;
	}
	return ans;
}


bool am_i_square(int N, int Q) {
    memo.clear();
	vector<vector<int>> qrys(4, vector<int>(4));

	int mx = 100, my = 100, Mx = -1, My = -1;

	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (query(i * 20, j * 20)) {
				mx = min(mx, i);
				my = min(my, j);
				Mx = max(Mx, i);
				My = max(My, j);
			}
		}
	}

	if (Mx == -1) {
		bool found = false;
		for (int i = 1; i <= 5; i++) {
			if (query(i * 20, 100)) {
				if (found) return false;
				found = true;

				int lb = searchLeft(i * 20, max(1, i * 20 - 19), 100);
				if (lb + 19 >= 100 || 
					!query(lb + 19, 100) || 
					(lb + 20 <= 100 && query(lb + 20, 100)) ||
					!query(i * 20, 81) ||
					query(i * 20, 80)
				) return false;
			}
		}

		for (int i = 1; i <= 4; i++) {
			if (query(100, i * 20)) {
				if (found) return false;
				found = true;
				
				int ub = searchUp(i * 20, i * 20 + 19, 100);
				if (!query(100, ub - 19) ||
					query(100, ub - 20) ||
					!query(81, i * 20) ||
					query(80, i * 20)
				) return false;
			}
		}

		return found;

	} else {
		int lb = searchLeft(mx * 20, max(1, mx * 20 - 19), my * 20);
		int rb = searchRight(Mx * 20, Mx * 20 + 20, my * 20);
		int ub = searchUp(My * 20, My * 20 + 20, mx * 20);
		int db = ub - rb + lb;

		if (db < 1 || 
			!query(mx * 20, db) ||
			(db - 1 >= 1 && query(mx * 20, db - 1))
		) return false;

		return true;
	}
}

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