Submission #41572

#	Time	Username	Problem	Language	Result	Execution time	Memory
41572		cheater2k	Chessboard (IZhO18_chessboard)	C++14	47 / 100	2045 ms	2480 KiB

chessboard

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

const int N = 1e5 + 5;

int n, k, nrec;
int lx[N], ly[N], rx[N], ry[N];
long long ans = 1e18;

int get(int t, int l, int r) {
    // count the number of x such that l <= x <= r and (x / k) % 2 == t
    if (l / k == r / k) {
        if ((l / k) % 2 == t) return r - l + 1; else return 0;
    }
    int ret = 0;

    if ((l / k) % 2 == t) ret += ((l / k) + 1) * k - l;
    if ((r / k) % 2 == t) ret += r - (r / k) * k + 1;
    
    l = (l / k) + 1;
    r = (r / k) - 1;

    if (l % 2 != t) ++l;
    if (r % 2 != t) --r;
    
    ret += max(0, (r - l) / 2 + 1) * k;

    return ret;
}

long long calc(int color, int lx, int ly, int rx, int ry) {
    // count the number of cells with (x + y) == color (modulo 2)
    int row[2] = {0, 0}, col[2] = {0, 0};
    for (int i = 0; i < 2; ++i) {
        row[i] = get(i, lx, rx);
        col[i] = get(i, ly, ry);
    }

    long long ret = 0;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) if ((i + j) % 2 == color) {
            ret += 1LL * row[i] * col[j];
        }
    }
    return ret;
}

void solve() {
    for (int t = 0; t < 2; ++t) {
        // black cells: (x, y) such that (x + y) == t (modulo 2)
        long long cur = calc(t, 0, 0, n - 1, n - 1); // number of black cells
        for (int i = 1; i <= nrec; ++i) {
            cur -= calc(t, lx[i], ly[i], rx[i], ry[i]); // black cells
            cur += calc(t ^ 1, lx[i], ly[i], rx[i], ry[i]); // white cells
        }
        ans = min(ans, cur);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> nrec;
    for (int i = 1; i <= nrec; ++i) {
        cin >> lx[i] >> ly[i] >> rx[i] >> ry[i];
        --lx[i]; --ly[i]; --rx[i]; --ry[i];
    }
    for (k = 1; k < n; ++k) if (n % k == 0) {
        solve();
    }
    cout << ans << endl;
}

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