Submission #677769

#	Time	Username	Problem	Language	Result	Execution time	Memory
677769		vjudge1	Chessboard (IZhO18_chessboard)	C++17	39 / 100	472 ms	5004 KiB

chessboard

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

#define int int64_t
#define x1 x1_
#define x2 x2_
#define y1 y1_
#define y2 y2_

const int N = 1e5 + 5;
const int BLACK_FIRST = 0;
const int WHITE_FIRST = 1;

// color of a ceil will be determined by (id row + id col) % 2 and the color of first block (BLACK_FIRST / WHITE_FIRST)
// in particular: (id row + id col) % 2 = BLACK_FIRST --> black id, otherwise ...
// id row = row div edge

int n, k;
int x[2][N], y[2][N];

void read() {
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> x[j][i] >> y[j][i];
      --x[j][i];
      --y[j][i];
    }
  }
}

int id_block (int x, int edge) {
  return x / edge;
}

// (0...x1) / k % 2 == type
int num_ceil (int x, int k, int type) {
  if (x < 0) {
    return 0;
  }
  if (x == 0) {
    return (x / k) % 2 == type;
  }
  int block_x = id_block(x, k);
  int ans = 0;

  if (block_x > 0) {
    // [0, block_x - 1]
    if (type == 0) {
      ans += (block_x - block_x / 2) * k;
    }
    else {
      ans += (block_x / 2) * k;
    }
  }

  // just in block_x
  int lo = block_x * k;
  int hi = x;

  if (block_x % 2 == type) {
    ans += (hi - lo + 1);
  }

  return ans;
}

int num_ceil (int l, int r, int k, int type) {
  assert(num_ceil(r, k, type) >= num_ceil(l - 1, k, type));
  return num_ceil(r, k, type) - num_ceil(l - 1, k, type);
}

int solve (int edge, int type) {
  int ans = 0;

  // (r + c) % 2 == type
  for (int row_type = 0; row_type < 2; row_type++) {
    int col_type = (type - row_type + 2) % 2;
    ans += num_ceil(0, n - 1, edge, row_type) * num_ceil(0, n - 1, edge, col_type);
  }

  for (int i = 1; i <= k; i++) {
    for (int row_type = 0; row_type < 2; row_type++) {
      for (int col_type = 0; col_type < 2; col_type++) {
        // already black
        // since we colored it before --> subtract
        if ((row_type + col_type) % 2 == type) {
          ans -= num_ceil(x[0][i], x[1][i], edge, row_type) * num_ceil(y[0][i], y[1][i], edge, col_type);
        }
        // must be white, but now it's black
        else {
          ans += num_ceil(x[0][i], x[1][i], edge, row_type) * num_ceil(y[0][i], y[1][i], edge, col_type);
        }
      }
    }
  }

  return ans;
}

void solve() {
  int best = 2e9;
  for (int edge = 1; edge < n; edge++) {
    if (n % edge) {
      continue;
    }
    best = min(best, solve(edge, BLACK_FIRST));
    best = min(best, solve(edge, WHITE_FIRST));
  }
  cout << best;
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  read();
  solve();

  return 0;
}

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