Submission #1170324

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

  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 = true;
  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: 0 / 14
• Subtask 2: 0 / 19
• Subtask 3: 18 / 18
• Subtask 4: 0 / 49