Submission #1151949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151949		Shadow1	Square or Rectangle? (NOI19_squarerect)	C++20	0 / 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 r = 0, c = 0;
	bool found = false;
	// Phase 1: Find a cell inside the shape: 25 queries
	for(int x=n/5; x<=n; x+=n/5) {  
		for(int y=n/5; y<=n; y+=n/5) {
			bool res = inside_shape(x, y);
			if(res) {
				r = y, c = x;
				found = true;
				break;
			}
		}
		if(found) break;
	}
	if(!found) return false;
	// Phase 2: Binary search up to determine height : log(rc) = 11 queries
	int h = 0, w = 0;
	int high = max(1, r-n/5), low = r;
	while(low < high) {
		int m = (low + high + 1) >> 1;
		if(inside_shape(r, m))
			low = m;
		else
			high = m+1;
	}
	// show(low);
	int high1 = n, low1 = r;
	while(low1 < high1) {
		int m = (low1 + high1 + 1) >> 1;
		if(inside_shape(r, m))
			low1 = m;
		else
			high1 = m-1;
	}
	// show(low1);
	h = (low1 - low) + 1;

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

	int left = max(1, c-n/5), right = c;
	while(left < right) {
		int m = (left + right) >> 1;
		if(inside_shape(m, c))
			right = m;
		else
			left = m+1;
	}
	// show(right);
	if(c-right+1 > h) return false;
	int p = c + h-(c-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(r, p);
	if(p < n) y2 = inside_shape(r, p+1);
	return (y1 && !y2 ? true : false);
}

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