Submission #634871

#	Time	Username	Problem	Language	Result	Execution time	Memory
634871		fabijan_cikac	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1850 ms	460 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

ll n, k; vector<ll> v;
ll num[100100];

ll mod(ll x, ll vel){
    if (x % vel == 0 && x != 0)
        return vel;
    return (x % vel);
}

bool black(ll x, ll y, ll vel){
    x -= mod(x, vel); y -= mod(y, vel);
    x /= vel; y /= vel;
    if ((x + y) & 1)
        return 0;
    return 1;
}

ll pref(ll x, ll y, ll vel){
    if (x == 0 || y == 0) return 0;
    ll ans = 0;
    ll x2 = x - mod(x, vel); ll y2 = y - mod(y, vel);
    ll val1 = x2 / vel; ll val2 = y2 / vel;
    ll p = val1 *  val2; ll u = p / 2;
    ans += -(p - u) * vel * vel + u * vel * vel;
    p = val2; u = p / 2; ll pt = 1;
    if (val1 % 2 == 0) pt = -1;
    ans += pt * (p - u) * vel * (x - x2) + -pt * u * vel * (x - x2);
    p = val1; u = p / 2; pt = 1;
    if (val2 % 2 == 0) pt = -1;
    ans += pt * (p - u) * vel * (y - y2) + -pt *  u * vel * (y - y2);
    if (black(x, y, vel))
        ans -= (x - x2) * (y - y2);
    else ans += (x - x2) * (y - y2);
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for (ll i = 1; i < n; ++i){
        if (n % i == 0){
            v.push_back(i);
            ll d = n / i;
            num[i] = (d * d + 1) / 2; num[i] *= i * i;
        }
    }
    for (int i = 0; i < k; ++i){
        ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        for (ll vel: v){
            num[vel] += (pref(x2, y2, vel) - pref(x2, y1 - 1, vel) - pref(x1 - 1, y2, vel) + pref(x1 - 1, y1 - 1, vel));
        }
    }
    ll sol = 1e18;
    for (ll x: v) sol = min(abs(sol), min(num[x], n * n - abs(num[x])));
    cout << sol;

    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