Submission #1170364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170364		mukundan314	Square or Rectangle? (NOI19_squarerect)	C++20	100 / 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 used = 0;

  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 < i; j += min_side) {
      if (used++, inside_shape(i, j)) {
        x = i, y = j;
        goto found;
      }

      if (used++, inside_shape(j, i)) {
        x = j, y = i;
        goto found;
      }
    }

    if (N < i + min_side)
      goto found;

    if (used++, inside_shape(i, i)) {
      x = i, y = i;
      goto found;
    }
  }

found:

  int lo, hi;

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

  x = lo;

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

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

  y = lo;

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

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

  int side = lo;

  bool valid = side != min_side - 1;
  if (valid && x + side - 1 <= N && y + side <= N)
    valid &= !inside_shape(x + side - 1, y + side);
  if (valid && 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: 49 / 49