oj.uz

Submission #317342

# Submission time Handle Problem Language Result Execution time Memory
317342 2020-10-29T14:38:21 Z sebinkim Square or Rectangle? (NOI19_squarerect) C++14
100 / 100
 1 ms 384 KB 
#include "squarerect.h"
#include <bits/stdc++.h>

using namespace std;

bool am_i_square(int N, int Q)
{
	auto ask = [&](int x, int y){
		if(x < 1 || x > N || y < 1 || y > N) return false;
		else return inside_shape(x, y);
	};

	int i, j, a, b, c, d;

	a = b = N; c = d = 1;
	for(i = 20; i < 100; i += 20){
		for(j = 20; j < 100; j += 20){
			if(ask(i, j)){
				a = min(a, i); b = min(b, j);
				c = max(c, i); d = max(d, j);
			}
		}
	}
	if(a == N){
		for(i = 20; i <= 100; i += 20){
			if(ask(i, N)){ a = i; break; }
			if(ask(N, i)){ b = i; break; }
		}
		for(i = 16; i >= 1; i >>= 1){
			if(ask(a + i, b)) a += i;
			if(ask(a, b + i)) b += i;
		}
		return ask(a - 19, b - 19) && !ask(a - 19, b - 20)
			&& !ask(a - 20, b - 19) && !ask(a - 20, b - 20);
	}
	else{
		for(i = 16; i >= 1; i >>= 1){
			if(ask(a - i, b)) a -= i;
			if(ask(a, b - i)) b -= i;
			if(ask(c + i, b)) c += i;
		}
		return ask(a, c - a + b) && !ask(a, c - a + b + 1);
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct