# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1216237 | Dzadzo | Square or Rectangle? (NOI19_squarerect) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "squarerect.h"
#define ll long long
// #define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 200000
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// bool inside_shape(int x,int y){
// cout<<x<<" "<<y<<'\n';
// bool res;
// cin>>res;
// return res;
// }
int N;
bool ask(int x,int y){
if (1<=x && x<=N && 1<=y && y<=N)return inside_shape(x,y);
return false;
}
bool am_i_square(int n, int q) {
N=n;
int Rmax=0,Rmin=INF,Cmax=0,Cmin=INF;
for (int i=20;i<=n;i+=20){
for (int j=20;j<=n;j+=20){
if (ask(i,j)){
Rmax=max(Rmax,i);
Cmax=max(Cmax,j);
Cmin=min(Cmin,j);
Rmin=min(Rmin,i);
}
}
}
if (!Rmax)return false;
if (Rmax-Rmin != Cmax - Cmin)return false;
int R=Rmax;
for (int bit=4;bit>=0;bit--){
if (R+(1<<bit) >= Rmax+20 )continue;
if (ask(R+(1<<bit)))R+=(1<<bit);
}
int R=Rmin;
for (int bit=4;bit>=0;bit--){
if (R-(1<<bit) <= Rmin-20 )continue;
if (ask(R-(1<<bit)))R-=(1<<bit);
}
int C=Cmax;
for (int bit=4;bit>=0;bit--){
if (C+(1<<bit) >= Cmax+20 )continue;
if (ask(C+(1<<bit)))C+=(1<<bit);
}
int C=Cmin;
for (int bit=4;bit>=0;bit--){
if (C-(1<<bit) <= Cmin-20 )continue;
if (ask(C-(1<<bit)))C-=(1<<bit);
}
return R-r == C-c
}
/*
signed main() {
ios::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
int tt;
cin>>tt;
while (tt--){
int n;
cin>>n;
int a[n+1];
for (int i=1;i<=n;i++)cin>>a[i];
}
}
*/