Submission #1170328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170328		mukundan314	Square or Rectangle? (NOI19_squarerect)	C++20	89.24 / 100	0 ms	328 KiB

squarerect

#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;

bool am_i_square(int N, int Q) {
  int min_fill = (N * N + 24) / 25;
  int min_side = std::ceil(std::sqrt(min_fill));

  int x = N, y = N;
  for (int i = min_side; i <= N; i += min_side) {
    for (int j = min_side; j <= N; j += min_side) {
      if (N < i + min_side && N < j + min_side)
        continue;
      if (inside_shape(i, j)) {
        x = i, y = j;
        goto found;
      }
    }
  }

found:

  int lo, hi;

  lo = x - min_side + 1, hi = x;
  while (lo < hi) {
    int mi = lo + (hi - lo) / 2;
    if (inside_shape(mi, y)) {
      hi = mi;
    } else {
      lo = mi + 1;
    }
  }

  x = lo;

  lo = y - min_side + 1, hi = y;
  while (lo < hi) {
    int mi = lo + (hi - lo) / 2;
    if (inside_shape(x, mi)) {
      hi = mi;
    } else {
      lo = mi + 1;
    }
  }

  y = lo;

  if (N < x + min_side - 1 || N < y + min_side - 1)
    return false;

  lo = min_side, hi = std::min(N - x, N - y) + 1;
  while (lo < hi) {
    int mi = lo + (hi - lo) / 2;
    if (!inside_shape(x + mi, y + mi)) {
      hi = mi;
    } else {
      lo = mi + 1;
    }
  }

  int side = lo;

  bool valid = inside_shape(x + side - 1, y + side - 1);
  if (x + side - 1 <= N && y + side <= N)
    valid &= !inside_shape(x + side - 1, y + side);
  if (x + side <= N && y + side - 1 <= N)
    valid &= !inside_shape(x + side, y + side - 1);
  return valid;
}

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