Submission #378524

#	Time	Username	Problem	Language	Result	Execution time	Memory
378524		syl123456	Chessboard (IZhO18_chessboard)	C++17	100 / 100	788 ms	4460 KiB

chessboard

#include <bits/stdc++.h>
#define all(i) i.begin(), i.end()
#define rall(i) i.rbegin(), i.rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
struct sq {
    int u, l, d, r;
    sq() = default;
    sq(int _u, int _l, int _d, int _r) : u(_u), l(_l), d(_d), r(_r) {}
};
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;
    sq a[k];
    for (sq &i : a) cin >> i.u >> i.l >> i.d >> i.r;
    auto calc = [](int d, int r, int len) {
        ll tmp[4];
        tmp[0] = 1ll * (d / len) * (r / len) / 2 * len * len;
        tmp[1] = 1ll * (r % len) * ((d / len + (r % (2 * len) < len ? 0 : 1)) / 2) * len;
        tmp[2] = 1ll * (d % len) * ((r / len + (d % (2 * len) < len ? 0 : 1)) / 2) * len;
        tmp[3] = ((d % (2 * len) < len) ^ (r % (2 * len) < len) ? 1ll * (d % len) * (r % len) : 0);
        return tmp[0] + tmp[1] + tmp[2] + tmp[3];
    };
    /*
     * 0101
     * 1010
     * 0101
     * 1010
     */
    ll ans = 1ll * n * n;
    for (int i = 1; i < n; ++i) if (n % i == 0) {
        ll cnt[4]{};
        for (int j = 0; j < k; ++j) {
            ll tmp = calc(a[j].d, a[j].r, i) - calc(a[j].d, a[j].l - 1, i) - calc(a[j].u - 1, a[j].r, i) + calc(a[j].u - 1, a[j].l - 1, i);
            cnt[3] += tmp;
            cnt[1] += 1ll * (a[j].d - a[j].u + 1) * (a[j].r - a[j].l + 1) - tmp;
        }
        cnt[2] = calc(n, n, i) - cnt[3];
        cnt[0] = 1ll * n * n - cnt[1] - cnt[2] - cnt[3];
        ans = min(ans, cnt[1] + cnt[2]);
        ans = min(ans, cnt[0] + cnt[3]);
    }
    cout << ans;
}

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