Submission #346934

#	Time	Username	Problem	Language	Result	Execution time	Memory
346934		milleniumEeee	Chessboard (IZhO18_chessboard)	C++17	70 / 100	269 ms	5868 KiB

chessboard

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

const int MAXN = (int)1e5 + 5;
const ll INF = (ll)1e18;

ll x[3][MAXN];
ll y[3][MAXN];
ll n, k;

ll dup(ll a, ll b) {
  return (a + b - 1ll) / b;
}

ll S(ll x) {
  return x * x;
}

ll sz_of_corner(ll n, ll len) {
  return (S(dup(n / len, 2)) + S((n / len) / 2ll)) * (len * len);
}

ll solve(ll len) {
  if (n == len) {
    return INF;
  }
  ll bad_white[2] = {0, 0};
  ll good_black[2] = {0, 0};
  for (int i = 1; i <= k; i++) {
    assert(x[1][i] == x[2][i] && y[1][i] == y[2][i]);
    int xx = dup(x[1][i], len);
    int yy = dup(y[1][i], len);
    // в правом левом углу черный цвет
    if ((xx + yy) % 2 == 0) { // черный цвет
      good_black[1]++;
    } else { // белый
      bad_white[1]++;
    }
    // в правом левом углу белый цвет
    if ((xx + yy) % 2 == 0) { // белый цвет
      bad_white[0]++;
    } else { // черный
      good_black[0]++;
    }
  }
  return min(bad_white[1] + sz_of_corner(n, len) - good_black[1],
  bad_white[0] + ((S(n) - sz_of_corner(n, len)) - good_black[0]));
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    cin >> x[1][i] >> y[1][i] >> x[2][i] >> y[2][i];
  }
  ll ans = INF;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ans = min(ans, solve(i));
      ans = min(ans, solve(n / i));
    }
  }
  cout << ans << endl;
}

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