Submission #395271

#	Time	Username	Problem	Language	Result	Execution time	Memory
395271		rama_pang	Chessboard (IZhO18_chessboard)	C++17	100 / 100	542 ms	4372 KiB

chessboard

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int n, k;
  cin >> n >> k;
  vector<array<int, 4>> rect;
  for (int i = 0; i < k; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--, b--, c--, d--;
    rect.push_back({a, b, c, d});
  }

  auto Solve = [&](int s) -> long long {
    long long res = 1ll * (n / s) * (n / s) / 2 * s * s;
    if (n / s % 2 == 1) {
      res += 1ll * s * s;
    }

    auto CountCorner = [&](int sx, int sy, int ex, int ey) -> long long {
      if (sx > ex || sy > ey) return 0;
      assert(sx / s == ex / s && sy / s == ey / s);
      if ((sx / s + sy / s) & 1) {
        return +1ll * (ex - sx + 1) * (ey - sy + 1);
      } else {
        return -1ll * (ex - sx + 1) * (ey - sy + 1);
      }
      return 0;
    };

    auto CountVertical = [&](int sx, int sy, int ex, int ey) -> long long {
      if (sx > ex || sy > ey) return 0;
      assert(sy / s == ey / s);
      assert((ex - sx + 1) % s == 0);
      int cnt = (ex - sx + 1) / s;
      if (cnt & 1) {
        if ((sx / s + sy / s) % 2 == 1) {
          return +1ll * (ey - sy + 1) * s;
        } else {
          return -1ll * (ey - sy + 1) * s;
        }
      }
      return 0;
    };

    auto CountHorizontal = [&](int sx, int sy, int ex, int ey) -> long long {
      if (sx > ex || sy > ey) return 0;
      assert(sx / s == ex / s);
      assert((ey - sy + 1) % s == 0);
      int cnt = (ey - sy + 1) / s;
      if (cnt & 1) {
        if ((sx / s + sy / s) % 2 == 1) {
          return +1ll * (ex - sx + 1) * s;
        } else {
          return -1ll * (ex - sx + 1) * s;
        }
      }
      return 0;
    };

    auto CountInside = [&](int sx, int sy, int ex, int ey) -> long long {
      if (sx > ex || sy > ey) return 0;
      int x = (ex - sx + 1) / s;
      int y = (ey - sy + 1) / s;
      if (x % 2 == 1 && y % 2 == 1) {
        if ((sx / s + sy / s) % 2 == 1) {
          return +1ll * s * s;
        } else {
          return -1ll * s * s;
        }
      }
      return 0;
    };

    for (int i = 0; i < k; i++) {
      if (rect[i][0] / s == rect[i][2] / s && rect[i][1] / s == rect[i][3] / s) {
        res += CountCorner(rect[i][0], rect[i][1], rect[i][2], rect[i][3]);
      } else if (rect[i][0] / s == rect[i][2] / s) {
        int sy = (rect[i][1] + s - 1) / s;
        int ey = (rect[i][3] + 1) / s;

        res += CountCorner(rect[i][0], rect[i][1], rect[i][2], s * sy - 1);
        res += CountCorner(rect[i][0], s * ey + 0, rect[i][2], rect[i][3]);

        res += CountHorizontal(rect[i][0], s * sy + 0, rect[i][2], s * ey - 1);
      } else if (rect[i][1] / s == rect[i][3] / s) {
        int sx = (rect[i][0] + s - 1) / s;
        int ex = (rect[i][2] + 1) / s;

        res += CountCorner(rect[i][0], rect[i][1], s * sx - 1, rect[i][3]);
        res += CountCorner(s * ex + 0, rect[i][1], rect[i][2], rect[i][3]);

        res += CountVertical(s * sx + 0, rect[i][1], s * ex - 1, rect[i][3]);
      } else {
        int sx = (rect[i][0] + s - 1) / s;
        int sy = (rect[i][1] + s - 1) / s;
        int ex = (rect[i][2] + 1) / s;
        int ey = (rect[i][3] + 1) / s;

        res += CountCorner(rect[i][0], rect[i][1], s * sx - 1, s * sy - 1);
        res += CountCorner(rect[i][0], s * ey + 0, s * sx - 1, rect[i][3]);
        res += CountCorner(s * ex + 0, rect[i][1], rect[i][2], s * sy - 1);
        res += CountCorner(s * ex + 0, s * ey + 0, rect[i][2], rect[i][3]);

        res += CountHorizontal(rect[i][0], s * sy + 0, s * sx - 1, s * ey - 1);
        res += CountHorizontal(s * ex + 0, s * sy + 0, rect[i][2], s * ey - 1);

        res += CountVertical(s * sx + 0, rect[i][1], s * ex - 1, s * sy - 1);
        res += CountVertical(s * sx + 0, s * ey + 0, s * ex - 1, rect[i][3]);

        res += CountInside(s * sx + 0, s * sy + 0, s * ex - 1, s * ey - 1);
      }
    }
    return min(res, 1ll * n * n - res);
  };

  long long ans = 1ll * n * n;
  for (int i = 1; i < n; i++) {
    if (n % i == 0) {
      ans = min(ans, Solve(i));
    }
  }
  cout << ans << "\n";
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30