Submission #342739

#	Time	Username	Problem	Language	Result	Execution time	Memory
342739		apostoldaniel854	Chessboard (IZhO18_chessboard)	C++14	100 / 100	691 ms	4452 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 1e5;
struct Rectangle {
    int x1;
    int y1;
    int x2;
    int y2;
};


int get_line (int n, int l) {
    return n / (2 * l) * l + min (n % (2 * l), l);
}

ll calc (int n, int m, int l) {
    int onX = get_line (n, l);
    int onY = get_line (m, l);
    return 1ll * onX * onY + 1ll * (n - onX) * (m - onY);
}

ll solve (int n, int l, vector <Rectangle> &rect) {
    ll black_answer = calc (n, n, l), white_answer = 1ll * n * n - black_answer;
    for (Rectangle r : rect) {
        int black = calc (r.x2, r.y2, l) - calc (r.x1 - 1, r.y2, l) - calc (r.x2, r.y1 - 1, l) + calc (r.x1 - 1, r.y1 - 1, l);
        int white = 1ll * (r.x2 - r.x1 + 1) * (r.y2 - r.y1 + 1) - black;
        black_answer -= black;
        black_answer += white;
        white_answer -= white;
        white_answer += black;
    }
    return min (white_answer, black_answer);
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, k;
    cin >> n >> k;
    vector <Rectangle> rect;
    for (int i = 1; i <= k; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rect.pb ({x1, y1, x2, y2});
    }
    ll ans = 1ll * n * n;
    for (int length = 1; length < n; length++)
        if (n % length == 0)
            ans = min (ans, solve (n, length, rect));
    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