제출 #609072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
609072		pakhomovee	Chessboard (IZhO18_chessboard)	C++17	70 / 100	745 ms	5692 KiB

chessboard

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <set>
#include <numeric>
#include <queue>
#include <functional>

using namespace std;

#define int long long

struct rect {
    int x1, y1, x2, y2;
    rect() {}
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<rect> r(k);
    int S = 0;
    for (int i = 0; i < k; ++i) {
        cin >> r[i].x1 >> r[i].y1 >> r[i].x2 >> r[i].y2;
        --r[i].x1; --r[i].y1; --r[i].x2; --r[i].y2;
        S += (r[i].x2 - r[i].x1 + 1) * (r[i].y2 - r[i].y1 + 1);
    }
    auto whiteCount = [&] (rect r, int len, int parity) {
        if (r.x1 / len == r.x2 / len && r.y1 / len == r.y2 / len) {
            int par = (r.x1 / len + r.y1 / len) % 2;
            if (par == parity) return (r.x2 - r.x1 + 1) * (r.y2 - r.y1 + 1);
            return 0ll;
        } else if (r.x1 / len == r.x2 / len) {
            int firstFullColumn = (r.y1 + len - 1) / len;
            int lastFullColumn = r.y2 / len;
            int res = 0;
            if ((r.x1 / len + r.y1 / len) % 2 == parity) {
                res += (firstFullColumn * len - r.y1) * (r.x2 - r.x1 + 1);
            }
            if ((r.x1 / len + lastFullColumn) % 2 == parity) {
                res += (r.y2 - lastFullColumn * len + 1) * (r.x2 - r.x1 + 1);
            }
            int par = (r.x1 / len + firstFullColumn) % 2 == parity;
            res += (lastFullColumn - firstFullColumn + par) / 2 * (r.x2 - r.x1 + 1) * len;
            return res;
        } else if (r.y1 / len == r.y2 / len) {
            swap(r.x1, r.y1);
            swap(r.x2, r.y2);
            int firstFullColumn = (r.y1 + len - 1) / len;
            int lastFullColumn = r.y2 / len;
            int res = 0;
            if ((r.x1 / len + r.y1 / len) % 2 == parity) {
                res += (firstFullColumn * len - r.y1) * (r.x2 - r.x1 + 1);
            }
            if ((r.x1 / len + lastFullColumn) % 2 == parity) {
                res += (r.y2 - lastFullColumn * len + 1) * (r.x2 - r.x1 + 1);
            }
            int par = (r.x1 / len + firstFullColumn) % 2 == parity;
            res += (lastFullColumn - firstFullColumn + par) / 2 * (r.x2 - r.x1 + 1) * len;
            return res;
        }
        int firstFullColumn = (r.y1 + len - 1) / len;
        int lastFullColumn = r.y2 / len;
        int firstFullRow = (r.x1 + len - 1) / len;
        int lastFullRow = r.x2 / len;
        int fullBlockPar = (firstFullRow + firstFullColumn) % 2;
        int res = ((lastFullColumn - firstFullColumn) * (lastFullRow - firstFullRow) + (fullBlockPar == parity)) / 2 * len * len;
        //  add corners
        int corner1 = 0, corner2 = 0, corner3 = 0, corner4 = 0;
        int up, down, lt, rt;
        up = firstFullRow * len - r.x1;
        down = r.x2 - lastFullRow * len + 1;
        lt = firstFullColumn * len - r.y1;
        rt = r.y2 - lastFullColumn * len + 1;
        if ((firstFullRow + firstFullColumn) % 2 == parity) {
            corner1 = up * lt;
        }
        if ((firstFullRow + lastFullColumn + 1) % 2 == parity) {
            corner2 = up * rt;
        }
        if ((lastFullRow + lastFullColumn) % 2 == parity) {
            corner3 = down * rt;
        }
        if ((lastFullRow + firstFullColumn + 1) % 2 == parity) {
            corner4 = down * lt;
        }
        res += corner1 + corner2 + corner3 + corner4;
        //  add borders
        int ltb = 0, rtb = 0, upb = 0, downb = 0;
        int ltp = (firstFullRow + firstFullColumn + 1) % 2 == parity;
        int rtp = (firstFullRow + lastFullColumn + 1) % 2 == parity;
        int upp = (firstFullRow + 1 + firstFullColumn) % 2 == parity;
        int downp = (lastFullRow + 1 + firstFullColumn) % 2 == parity;
        ltb = (lastFullRow - firstFullRow + 1 + ltp) / 2 * lt * len;
        rtb = (lastFullRow - firstFullRow + 1 + rtp) / 2 * rt * len;
        upb = (lastFullColumn - firstFullColumn + 1 + upp) / 2 * up * len;
        downb = (lastFullColumn - firstFullColumn + 1 + downp) / 2 * down * len;
        res += ltb + rtb + upb + downb;
        return res;
    };
    int ans = n * n;
    for (int len = 1; len < n; ++len) {
        if (n % len) continue;
        if (1) {
            int cntSide = n / len;
            int black = (cntSide * cntSide + 1) / 2 * len * len;
            int wrongWhite = 0;
            for (rect q : r) {
                wrongWhite += whiteCount(q, len, 1);
            }
            ans = min(ans, wrongWhite * 2 + black - S);
        }
        if (1) {
            int cntSide = n / len;
            int black = (cntSide * cntSide) / 2 * len * len;
            int wrongWhite = 0;
            for (rect q : r) {
                wrongWhite += whiteCount(q, len, 0);
            }
            ans = min(ans, wrongWhite * 2 + black - S);
        }
    }
    cout << ans;
}
/*
 6 8
 3 3 3 3
 1 2 1 2
 3 4 3 4
 5 5 5 5
 4 3 4 3
 4 4 4 4
 2 1 2 1
 3 6 3 6
*/

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