Submission #1298392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298392		SamNguyen	Square or Rectangle? (NOI19_squarerect)	C++20	Compilation error	0 ms	0 KiB

squarerect

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

struct BinarySearch
{
	using F = function<bool(int)>;

	F pred;
	BinarySearch(F f) : pred(f) {}

	int lower_bound(int min_v, int max_v, bool flipped = false)
	{
		int res_v = max_v + 1;
		while (min_v <= max_v)
		{
			int mid_v = (min_v + max_v) >> 1;
			if (pred(mid_v) ^ flipped)
				res_v = mid_v, max_v = mid_v - 1;
			else
				min_v = mid_v + 1;
		}
		return res_v;
	}

	int upper_bound(int min_v, int max_v, bool flipped = false)
	{
		int res_v = min_v - 1;
		while (min_v <= max_v)
		{
			int mid_v = (min_v + max_v) >> 1;
			if (pred(mid_v) ^ flipped)
				res_v = mid_v, min_v = mid_v + 1;
			else
				max_v = mid_v - 1;
		}
		return res_v;
	}
};

const int MAX = 100 + 2;
struct Problem
{
	static int memo[MAX][MAX];
	int N, Q, DIVIDERS, BLOCK_LEN;

	Problem(int n, int q, int DIVIDERS) : N(n), Q(q), DIVIDERS(DIVIDERS)
	{
		BLOCK_LEN = N / DIVIDERS;
		memset(memo, -1, sizeof memo);
	}

	inline bool inside_shape_safe(int x, int y)
	{
		if (memo[x][y] == -1)
			memo[x][y] = inside_shape(x, y);
		return memo[x][y];
	}

	inline pair<int, int> master_grid(int i, int j)
	{
		return make_pair(i * BLOCK_LEN + 1, j * BLOCK_LEN + 1);
	}

	bool solve_large_from_cell(int x, int y)
	{
		BinarySearch bs_by_x([&](int t)
							 { return inside_shape_safe(t, y); });
		BinarySearch bs_by_y([&](int t)
							 { return inside_shape_safe(x, t); });

		int left = bs_by_x.lower_bound(1, x - 1);
		int right = bs_by_x.lower_bound(x + 1, N, true);
		int top = bs_by_y.lower_bound(1, y - 1);
		int bottom = bs_by_y.lower_bound(y + 1, N, true);
		return right - left == bottom - top;
	}

	bool solve_small_from_cell(int x, int y)
	{
		// BinarySearch bs_pad_x([&](int pad)
		// 					  { return inside_shape_safe(x - BLOCK_LEN + pad, y) and inside_shape_safe(x + BLOCK_LEN - pad, y); });
		// BinarySearch bs_pad_y([&](int pad)
		// 					  { return inside_shape_safe(x, y - BLOCK_LEN + pad) and inside_shape_safe(x, y + BLOCK_LEN - pad); });

		// int pad_x = bs_pad_x.lower_bound(1, BLOCK_LEN / 2);
		// int pad_y = bs_pad_y.lower_bound(1, BLOCK_LEN / 2);

		BinarySearch bs_by_x([&](int t)
							 { return inside_shape_safe(t, y); });
		BinarySearch bs_by_y([&](int t)
							 { return inside_shape_safe(x, t); });

		int left = bs_by_x.lower_bound(x - BLOCK_LEN + 1, x - 1);
		int right = bs_by_x.lower_bound(x + 1, x + BLOCK_LEN - 1, true);
		int top = bs_by_y.lower_bound(y - BLOCK_LEN + 1, y - 1);
		int bottom = bs_by_y.lower_bound(y + 1, y + BLOCK_LEN - 1, true);
		return right - left == bottom - top;

		return false;
	}
};

bool am_i_square(int N, int Q)
{
	Problem problem(N, Q, 5);

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			if ((i + j) % 2 == 1)
			{
				int x, y;
				tie(x, y) = problem.master_grid(i, j);
				if (inside_shape(x, y))
					return problem.solve_large_from_cell(x, y);
			}

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			if ((i + j) % 2 == 0)
			{
				int x, y;
				tie(x, y) = problem.master_grid(i, j);
				if (inside_shape(x, y))
					return problem.solve_small_from_cell(x, y);
				// return problem.solve_large_from_cell(x, y);
			}

	return false;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccNcsNh6.o: in function `am_i_square(int, int)':
squarerect.cpp:(.text+0x50): undefined reference to `Problem::memo'
/usr/bin/ld: /tmp/ccNcsNh6.o: in function `std::_Function_handler<bool (int), Problem::solve_small_from_cell(int, int)::{lambda(int)#1}>::_M_invoke(std::_Any_data const&, int&&)':
squarerect.cpp:(.text._ZNSt17_Function_handlerIFbiEZN7Problem21solve_small_from_cellEiiEUliE_E9_M_invokeERKSt9_Any_dataOi[_ZNSt17_Function_handlerIFbiEZN7Problem21solve_small_from_cellEiiEUliE_E9_M_invokeERKSt9_Any_dataOi]+0xb): undefined reference to `Problem::memo'
/usr/bin/ld: /tmp/ccNcsNh6.o: in function `std::_Function_handler<bool (int), Problem::solve_large_from_cell(int, int)::{lambda(int)#1}>::_M_invoke(std::_Any_data const&, int&&)':
squarerect.cpp:(.text._ZNSt17_Function_handlerIFbiEZN7Problem21solve_large_from_cellEiiEUliE_E9_M_invokeERKSt9_Any_dataOi[_ZNSt17_Function_handlerIFbiEZN7Problem21solve_large_from_cellEiiEUliE_E9_M_invokeERKSt9_Any_dataOi]+0xb): undefined reference to `Problem::memo'
/usr/bin/ld: /tmp/ccNcsNh6.o: in function `std::_Function_handler<bool (int), Problem::solve_small_from_cell(int, int)::{lambda(int)#2}>::_M_invoke(std::_Any_data const&, int&&)':
squarerect.cpp:(.text._ZNSt17_Function_handlerIFbiEZN7Problem21solve_small_from_cellEiiEUliE0_E9_M_invokeERKSt9_Any_dataOi[_ZNSt17_Function_handlerIFbiEZN7Problem21solve_small_from_cellEiiEUliE0_E9_M_invokeERKSt9_Any_dataOi]+0x8): undefined reference to `Problem::memo'
/usr/bin/ld: /tmp/ccNcsNh6.o: in function `std::_Function_handler<bool (int), Problem::solve_large_from_cell(int, int)::{lambda(int)#2}>::_M_invoke(std::_Any_data const&, int&&)':
squarerect.cpp:(.text._ZNSt17_Function_handlerIFbiEZN7Problem21solve_large_from_cellEiiEUliE0_E9_M_invokeERKSt9_Any_dataOi[_ZNSt17_Function_handlerIFbiEZN7Problem21solve_large_from_cellEiiEUliE0_E9_M_invokeERKSt9_Any_dataOi]+0x8): undefined reference to `Problem::memo'
collect2: error: ld returned 1 exit status