Submission #1151971

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

squarerect

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

using ll = long long;

#define i64 int64_t
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << '\n';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define vt vector
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define fir first
#define sec second
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());

// Total: 42 queries
bool am_i_square(int N, int Q) {
	int n = N;
	int x = 0, y = 0;
	bool found = false;
	// Phase 1: Find a cell inside the shape: 25 queries
	for(int i=n/5; i<=n; i+=n/5) {  
		for(int j=n/5; j<=n; j+=n/5) {
			bool res = inside_shape(i, j);
			if(res) {
				x = i, y = j;
				found = true;
				break;
			}
		}
		if(found) break;
	}
	// show(x);
	// show(y);
	if(!found) return false;
	// Phase 2: Binary search up to determine height : log(rc) = 11 queries
	int h = 0, w = 0;
	int up = max(1, y-n/5), down = y;
	while(up < down) {
		int m = (up + down) >> 1;
		if(inside_shape(x, m))
			down = m;
		else
			up = m+1;
	}
	// show(down);
	int high1 = n, low1 = y;
	while(low1 < high1) {
		int m = (low1 + high1 + 1) >> 1;
		if(inside_shape(x, m))
			low1 = m;
		else
			high1 = m-1;
	}
	// show(low1);
	h = (low1 - down) + 1;

	// Phase 3: Determine width: log2(n) = 4 queries

	int left = max(1, x-n/5), right = x;
	while(left < right) {
		int m = (left + right) >> 1;
		if(inside_shape(m, y))
			right = m;
		else
			left = m+1;
	}
	// show(right);
	if(x-right+1 > h) return false;
	int p = x + h-(x-right+1);
	// show(p);
	if(p > n) return false;
	// Last 2 queries

	bool y1 = false, y2 = false;
	if(p == n) y2 = false;
	y1 = inside_shape(p, y);
	if(p < n) y2 = inside_shape(p+1, y);
	return (y1 && !y2 ? true : false);
}

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