Background

Translated from NOISG2019 Prelim D.Square or Rectangle?。

Please note that this problem is interactive. Please try to use C++ to solve it. Also, you only need to implement the function required in the statement. Do not output your answer to standard output.

For contestants using non-C++ languages, there is an interactive I/O version: https://www.luogu.com.cn/problem/P15054, where you can submit for evaluation.

Problem Description

You are given an $N \times N$ grid. Inside the grid, there is one rectangle that occupies at least $4\%$ of the total grid area. However, you do not know whether this rectangle is a rectangle (non-square) or a square. You need to define a function to solve this problem.

Implementation Details

You need to define the following function:

bool am_i_square(int N, int Q)

• $N$: the size of the grid.
• $Q$: the number of queries you are allowed to ask the judge.

To determine the shape, you may call the judge function bool inside_shape(int X, int Y) at most $Q$ times. Call it to ask whether cell $(X, Y)$ is inside the rectangle.

Once you have determined the shape, you can return a bool value indicating whether the rectangle is a square.

The judge will call your function $T$ times. The value of $T$ can be found in Constraints and Scoring.

Input Format

See Implementation Details.

Output Format

See Implementation Details.

Hint

Sample

Consider the following calls:

am_i_square(5, 25)

This means the grid size is $5 \times 5$, and you may call inside_shape at most $25$ times.

inside_shape(3, 3) = true

This asks whether cell $(3, 3)$ is inside the rectangle. It is at the center of the square, so it returns true.

inside_shape(5, 4) = false

This asks whether cell $(5, 4)$ is inside the rectangle. It is not inside the square, so it returns false.

inside_shape(1, 1) = false

This asks whether cell $(1, 1)$ is inside the rectangle. It is not inside the square, so it returns false.

inside_shape(2, 4) = true

This asks whether cell $(2, 4)$ is inside the rectangle. It is at the bottom-left corner of the square, so it returns true.

Therefore, we can determine that it is a square, so the function returns true.

Constraints and Scoring

For $100\%$ of the testdata: $N = 100$, $1 \leq T \leq 1000$.

Scoring for Subtask 3

Let $q$ be the maximum number of queries you used among all calls.

• If $q > 50$, you get $0$ points.
• If $34 \leq q \leq 50$, you get $40 - 30 \times \frac{q - 34}{17}$ points.
• If $q \leq 33$, you get full points.

Notes

Please add the following before your function:

#include <bits/stdc++.h>
using namespace std;
extern "C" bool inside_shape(int x,int y);

Also, add extern "C" before your bool am_i_square(int N, int Q).

Translated by ChatGPT 5