Submission #1112641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112641		MisterReaper	Chessboard (IZhO18_chessboard)	C++17	100 / 100	323 ms	5784 KiB

chessboard

#include <bits/stdc++.h>
 
using i64 = long long;
 
#ifdef DEBUG 
    #include "../../../debug.h"
#else
    #define debug(...) void(23)
#endif

i64 get(i64 a, i64 b, i64 len) {
    i64 ans = 0;
    i64 ma = a % (2 * len);
    i64 mb = b % (2 * len);
    i64 da = a / (2 * len);
    i64 db = b / (2 * len);
    ans += da * db * len * len * 2;
    ans += mb * da * len;
    ans += ma * db * len;
    ans += std::max(0LL, mb - len) * std::min(len, ma);
    ans += std::max(0LL, ma - len) * std::min(len, mb);
    debug(a, b, len, ans);
    return ans;
}

i64 count_good(i64 a, i64 b, i64 c, i64 d, i64 len) {
    return get(c, d, len)
         - get(a, d, len)
         - get(c, b, len)
         + get(a, b, len);
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    i64 N, K;
    std::cin >> N >> K;
    std::vector<i64> A(K), B(K), C(K), D(K);
    for (int i = 0; i < K; ++i) {
        std::cin >> A[i] >> B[i] >> C[i] >> D[i];
        --A[i], --B[i];
    }
 
    i64 ans = 2 * N * N;
    for (i64 k = 1; k < N; ++k) {
        if (N % k != 0) {
            continue;
        }
        i64 now = N * N - count_good(0, 0, N, N, k);
        for (int i = 0; i < K; ++i) {
            i64 x = count_good(A[i], B[i], C[i], D[i], k);
            debug(A[i], B[i], C[i], D[i], x);
            now -= ((C[i] - A[i]) * (D[i] - B[i]) - x);
            now += x;
        }
        debug(k, now);
        ans = std::min(ans, std::min(now, N * N - now));
    }
    std::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