Submission #1168501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168501		avighna	Square or Rectangle? (NOI19_squarerect)	C++20	100 / 100	3 ms	324 KiB

squarerect

#include <bits/stdc++.h>

bool inside_shape(int X, int Y);

bool am_i_square(int N, int Q) {
  std::vector asked(N + 1, std::vector<bool>(N + 1)), q(N + 1, std::vector<bool>(N + 1));
  auto query = [&](int x, int y) -> bool {
    if (x < 1 or x > N or y < 1 or y > N) {
      return false;
    }
    if (asked[x][y]) {
      return q[x][y];
    }
    asked[x][y] = true;
    bool left = false, top = false;
    for (int i = 0; i < N; ++i) {
      left = left or q[i][y];
      top = top or q[x][i];
    }
    if (left and top) {
      return q[x][y] = true;
    }
    return q[x][y] = inside_shape(x, y);
  };

  const int gap = N / 5;

  std::pair<int, int> t_l, t_r;
  bool at_least_one = false;
  for (int i = gap + 1; i <= N; i += gap) {
    for (int j = gap + 1; j <= N; j += gap) {
      if (!query(i, j)) {
        continue;
      }
      at_least_one = true;
      if (t_l.first == 0) {
        t_l = {i, j};
      }
      if (t_l.first == i) {
        t_r = {i, j};
      }
    }
  }

  auto binary_search = [&](const std::function<bool(int)> &f, int s, int d) {
    int del = 0;
    for (int i = 1 << int(std::log2(gap)); i >= 1; i /= 2) {
      if (del + i <= gap) {
        del += i * f(s + d * (del + i));
      }
    }
    return s + d * del;
  };

  if (at_least_one) {
    int TL_x = binary_search([&](int i) { return query(t_l.first, i); }, t_l.second, -1);
    int TR_x = binary_search([&](int i) { return query(t_r.first, i); }, t_r.second, 1);
    int TL_y = binary_search([&](int i) { return query(i, TL_x); }, t_l.first, -1);
    int len = TR_x - TL_x + 1;
    return query(TL_y + len - 1, TL_x) and !query(TL_y + len, TL_x);
  } else {
    int cnt = 0;
    for (int i = 1; i <= N; i += gap) {
      for (int j = 1; j <= N; j += gap) {
        cnt += (i == 1 or j == 1) and query(i, j);
      }
    }
    return cnt == 1;
  }
}

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