Submission #1229382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229382		trufanov.p	Chessboard (IZhO18_chessboard)	C++20	100 / 100	210 ms	4648 KiB

chessboard

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

const ll INF = 1e18;

struct Rectangle {
    ll x1, y1, x2, y2;
    Rectangle(ll x1_, ll y1_, ll x2_, ll y2_) :x1(x1_), y1(y1_), x2(x2_), y2(y2_) {}
    ll area() const {
        return (x2 - x1 + 1) * (y2 - y1 + 1);
    }
};

//0 - white, 1 - black

ll paint(ll d, ll n, const Rectangle& r) {
    ll dim1 = r.x2 - r.x1 + 1, dim2 = r.y2 - r.y1 + 1;
    ll ans = 0;
    ll xr1 = r.x1 / d, yr1 = r.y1 / d;
    ll xr2 = r.x2 / d, yr2 = r.y2 / d;
    ll xfull1 = xr1 + 1, yfull1 = yr1 + 1;
    ll xfull2 = xr2 - 1, yfull2 = yr2 - 1;
    if (xfull1 <= xfull2 && yfull1 <= yfull2) {
        ll color = (xfull1 + yfull1) % 2;
        ll d1 = (xfull2 - xfull1 + 1), d2 = (yfull2 - yfull1 + 1);
        if (d1 % 2 == 1 && d2 % 2 == 1) {
            ans += ((d1 * d2) / 2 + (color == 0)) * (d * d);
        } else {
            ans += ((d1 * d2) / 2) * (d * d);
        }
    }
    if (yfull1 <= yfull2) {
        ll uph = min(d - r.x1 % d, dim1);
        ll color = 1 - (xr1 + yr1) % 2;
        ll d2 = (yfull2 - yfull1 + 1);
        if (d2 % 2 == 1) {
            ans += ((d2 / 2) + (color == 0)) * uph * d;
        } else {
            ans += (d2 / 2) * uph * d;
        }
        if (xr1 != xr2) {
            //ll downh = (r.x2 % d == 0 ? d : r.x2 % d);
            ll downh = min(r.x2 % d + 1, dim1);
            color = 1 - (xr2 + yr1) % 2;
            if (d2 % 2 == 1) {
                ans += ((d2 / 2) + (color == 0)) * downh * d;
            } else {
                ans += (d2 / 2) * downh * d;
            }
        }
    }
    if (xfull1 <= xfull2) {
        ll lefth = min(d - r.y1 % d, dim2);
        ll color = 1 - (xr1 + yr1) % 2;
        ll d1 = (xfull2 - xfull1 + 1);
        if (d1 % 2 == 1) {
            ans += ((d1 / 2) + (color == 0)) * lefth * d;
        } else {
            ans += (d1 / 2) * lefth * d;
        }
        if (yr1 != yr2) {
            //ll righth = (r.y2 % d == 0 ? d : r.y2 % d);
            ll righth = min(r.y2 % d + 1, dim2);
            color = 1 - (xr1 + yr2) % 2;
            if (d1 % 2 == 1) {
                ans += ((d1 / 2) + (color == 0)) * righth * d;
            } else {
                ans += (d1 / 2) * righth * d;
            }
        }
    }
    ll color = (xr1 + yr1) % 2;
    ans += (color == 0) * min(d - r.x1 % d, dim1) * min(d - r.y1 % d, dim2);
    if (yr1 != yr2) {
        color = (xr1 + yr2) % 2;
        //ans += (color == 0) * (d - r.x1 % d) * (r.y2 % d == 0 ? d : r.y2 % d);
        ans += (color == 0) * min(d - r.x1 % d, dim1) * min(r.y2 % d + 1, dim2);
    }
    if (xr1 != xr2) {
        color = (xr2 + yr1) % 2;
        //ans += (color == 0) * (r.x2 % d == 0 ? d : r.x2 % d) * (d - r.y1 % d);
        ans += (color == 0) * min(r.x2 % d + 1, dim1) * min(d - r.y1 % d, dim2);
    }
    if (xr1 != xr2 && yr1 != yr2) {
        color = (xr2 + yr2) % 2;
        //ans += (color == 0) * (r.x2 % d == 0 ? d : r.x2 % d) * (r.y2 % d == 0 ? d : r.y2 % d);
        ans += (color == 0) * min(r.x2 % d + 1, dim1) * min(r.y2 % d + 1, dim2);
    }
    return ans;
}

ll calc(ll d, ll n, const vector<Rectangle>& rect) {
    ll answhite = 0, ansblack = 0;
    ll cnt = n / d;
    ll needwhite = (cnt * cnt) / 2 * d * d, needblack = n * n - needwhite;
    for (const auto& r : rect) {
        ll cur = paint(d, n, r);
        answhite += cur;
        ansblack += r.area() - cur;
        needwhite -= (r.area() - cur);
        needblack -= cur;
    }
    answhite += needwhite;
    ansblack += needblack;
    return min(answhite, ansblack);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    int k;
    cin >> n >> k;
    vector<Rectangle> rect;
    for (int i = 0; i < k; ++i) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rect.push_back(Rectangle(x1 - 1, y1 - 1, x2 - 1, y2 - 1));
    }
    ll ans = INF;
    for (ll d = 1; d * d <= n; ++d) {
        if (n % d == 0) {
            ans = min(ans, calc(d, n, rect));
            if (d != 1 && d * d != n) {
                ans = min(ans, calc(n / d, n, rect));
            }
        }
    }
    cout << ans << '\n';
}

/*
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
*/

/*
4 1
4 1 4 4
*/

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