oj.uz

Submission #317341

# Submission time Handle Problem Language Result Execution time Memory
317341 2020-10-29T14:36:30 Z sebinkim Square or Rectangle? (NOI19_squarerect) C++14
80.4118 / 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(; a != N && ask(a + 1, b); a ++);
		for(; b != N && ask(a, b + 1); b ++);
		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 384 KB Output is correct

Subtask #2
19.0 / 19.0

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

Subtask #3
18.0 / 18.0

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

Subtask #4
29.411764704 / 49.0

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