Submission #523572

#	Time	Username	Problem	Language	Result	Execution time	Memory
523572		RaresFelix	Chessboard (IZhO18_chessboard)	C++17	47 / 100	2061 ms	1796 KiB

chessboard

#include <iostream>
#include <climits>
#include <tuple>
#include <vector>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define MN 107171

using namespace std;
using ll = long long;
ll n, k;
tuple<int, int, int, int> R[MN];

static inline ll calc(ll a, ll b, ll l) {
    if(a % l == 0 && b % l == 0)
        return ((a / l) * (b / l) + 1) / 2 * l * l;
    if(a % l) {
        ll nrseg;
        if(a / l % 2ll == 0) {
            if(b % (2ll * l) <= l) nrseg = (b / (2ll * l)) * l + b % (2 * l);
            else nrseg = (b / (2ll * l) + 1) * l;
        } else {
            if(b % (2ll * l) <= l) nrseg = (b / (2ll * l)) * l;
            else nrseg = (b / (2ll * l) - 1) * l + b % (2 * l);
        }
        return calc(a - (a % l), b, l) + (a % l) * nrseg;
    }
    return calc(b, a, l);
}
ll sol(ll l) {
    ll arie = ((n / l) * (n / l) + 1) / 2 * l * l, selec;
    for(int i = 1; i <= k; ++i) {
        auto &[a, b, c, d] = R[i];
        selec = calc(c, d, l) + calc(a-1, b-1, l) - calc(c, b-1, l) - calc(a-1, d, l);
        arie += (c - a + 1) * (d - b + 1) - 2 * selec;
    }
    return min(arie, 1ll * n * n - arie);
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 1, a, b, c, d; i <= k; ++i)
        cin >> a >> b >> c >> d, R[i] = make_tuple(a, b, c, d);
    ll re = LLONG_MAX;
    for(int i = 1; i < n; ++i)
        if(n % i == 0) re = min(re, sol(i));
    cout << re << "\n";
}

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