Submission #715008

#	Time	Username	Problem	Language	Result	Execution time	Memory
715008		Stickfish	Chessboard (IZhO18_chessboard)	C++17	70 / 100	615 ms	1872 KiB

chessboard

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

bool get_color(pair<int, int> p, int d) {
    return (p.first / d + p.second / d) & 1;
}

ll intersect(pair<pair<int, int>, pair<int, int>> r1, pair<pair<int, int>, pair<int, int>> r2) {
    ll w = min(r1.second.first, r2.second.first) - max(r1.first.first, r2.first.first);
    ll h = min(r1.second.second, r2.second.second) - max(r1.first.second, r2.first.second);
    if (w < 0 || h < 0)
        return 0;
    return w * h;
}

signed main() {
    ll n, k;
    cin >> n >> k;
    vector<pair<pair<int, int>, pair<int, int>>> rect(k);
    for (int i = 0; i < k; ++i) {
        cin >> rect[i].first.first >> rect[i].first.second >> rect[i].second.first >> rect[i].second.second;
        --rect[i].first.first, --rect[i].first.second, --rect[i].second.first, --rect[i].second.second;
    }
    vector<ll> divs;
    for (int p = 1; p < n; ++p) {
        if (n % p == 0)
            divs.push_back(p);
    }
    int szd = divs.size();
    vector<ll> ans(szd);
    for (int di = 0; di < szd; ++di) {
        ll d = divs[di];
        if (n / d == 0)
            ans[di] = n * n / 2;
        else
            ans[di] = d * d * ((n / d) * (n / d) / 2);
    }
    for (auto [ld, ru] : rect) {
        for (int di = 0; di < szd; ++di) {
            ll d = divs[di];
            int r = ld.first + (ru.first - ld.first) % (2 * d);
            int u = ld.second + (ru.second - ld.second) % (2 * d);
            pair<pair<int, int>, pair<int, int>> rct = {ld, {r + 1, u + 1}};

            ll bi = ld.first / (2 * d) * (2 * d);
            ll bj = ld.second / (2 * d) * (2 * d);
            ans[di] += intersect(rct, {{bi, bj}, {bi + d, bj + d}});
            ans[di] -= intersect(rct, {{bi + d, bj}, {bi + 2 * d, bj + d}});
            ans[di] -= intersect(rct, {{bi, bj + d}, {bi + d, bj + 2 * d}});
            ans[di] += intersect(rct, {{bi + d, bj + d}, {bi + 2 * d, bj + 2 * d}});
        }
    }
    ll mnans = n * n;
    for (auto x : ans) {
        mnans = min({mnans, x, n * n - x});
    }
    cout << mnans << '\n';
}

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