Submission #173862

#	Time	Username	Problem	Language	Result	Execution time	Memory
173862		VEGAnn	Chessboard (IZhO18_chessboard)	C++14	62 / 100	1853 ms	4368 KiB

chessboard

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int, int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int oo = 2e9;
const ll OO = 1e18;
const int N = 100100;
ll ans = OO, gl;
int x1[N], Y1[N], x2[N], y2[N], n, k;

ll calc(ll x, ll y){
    if (x <= 0 || y <= 0) return 0;
    ll kl = y / gl, res = 0;
    ll ko = x / gl;

    ll ad1 = 0, ad2 = 0;

    if (x % gl > 0){
        if (ko % 2 == 0)
            ad1 += x % gl;
        else ad2 += x % gl;
    }

    res += ((kl + 1) / 2ll) * gl * ((ko + 1) / 2ll * gl + ad1);
    res += ((kl + 0) / 2ll) * gl * ((ko + 0) / 2ll * gl + ad2);

    if (y % gl > 0){
        if (kl % 2 == 0)
            res += ((ko + 1) / 2ll * gl + ad1) * (y % gl);
        else res += ((ko + 0) / 2ll * gl + ad2) * (y % gl);
    }

    return res;
}

ll calc(ll x1, ll Y1, ll x2, ll y2){
    return calc(x2, y2) - calc(x1 - 1, y2) - calc(x2, Y1 - 1) + calc(x1 - 1, Y1 - 1);
}

ll check(ll x){
    gl = x;
    ll cnd1 = calc(n, n);
    ll cnd2 = ll(n) * ll(n) - cnd1;

    for (int i = 0; i < k; i++){
        ll k1 = calc(x1[i], Y1[i], x2[i], y2[i]);
        ll x = x2[i] - x1[i] + 1;
        ll y = y2[i] - Y1[i] + 1;
        cnd1 -= k1 - (x * y - k1);
        cnd2 -= - k1 + (x * y - k1);
    }

    return min(cnd1, cnd2);
}

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

    cin >> n >> k;

    if (k == 0){
        for (int i = n - 1; ;i--)
            if (n % i == 0){
                n /= i;
                int res = (n * n) / 2;
                cout << res * i * i;
                break;
            }
        return 0;
    }

    for (int i = 0; i < k; i++)
        cin >> x1[i] >> Y1[i] >> x2[i] >> y2[i];

    int root = (int)trunc(sqrt(n));
    for (int i = 1; i <= root; i++)
        if (n % i == 0){
            ans = min(ans, check(i));
            if (i != 1)
                ans = min(ans, check(n / i));
        }

    cout << ans;

    return 0;
}

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