Submission #90899

#	Time	Username	Problem	Language	Result	Execution time	Memory
90899		toloraia	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1178 ms	34588 KiB

chessboard

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll N = 1e5 + 5;

ll n, k;
ll x[N], y[N], X[N], Y[N];
ll a[2][2];
ll S1, S2;
ll ans;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for (ll i = 1; i <= k; i++){
        cin>>x[i]>>y[i]>>X[i]>>Y[i];
        x[i]--;
        y[i]--;
        X[i]--;
        Y[i]--;
        S1 += (X[i] - x[i] + 1) * (Y[i] - y[i] + 1);
    }
    S2 = n * n - S1;
    ans = n * n;
    for (ll I = 1; I < n; I++)
        if (n % I == 0){
            ll s1 = ((n / I) * (n / I) + 1) / 2 * I * I, s2 = (n / I) * (n / I) / 2 * I * I;
            ll m1 = 0, m2 = 0;
            for (ll i = 1; i <= k; i++){
                for (ll j = 0; j < 2; j++)
                    for (ll l = 0; l < 2; l++)
                        a[j][l] = 0;
                ll p, q, t;
                p = (x[i] + I - 1) / I * I;
                if (X[i] < p)
                    a[0][(x[i] / I) % 2] += X[i] - x[i] + 1;
                else {
                    q = X[i] / I * I;
                    t = (q - p) / I;
                    a[0][(x[i] / I) % 2] += p - x[i];
                    a[0][(X[i] / I) % 2] += X[i] - q + 1;
                    a[0][(p / I) % 2] += (t + 1) / 2 * I;
                    a[0][(p / I + 1) % 2] += t / 2 * I;
                }
                p = (y[i] + I - 1) / I * I;
                if (Y[i] < p)
                    a[1][(y[i] / I) % 2] += Y[i] - y[i] + 1;
                else {
                    q = Y[i] / I * I;
                    t = (q - p) / I;
                    a[1][(y[i] / I) % 2] += p - y[i];
                    a[1][(Y[i] / I) % 2] += Y[i] - q + 1;
                    a[1][(p / I) % 2] += (t + 1) / 2 * I;
                    a[1][(p / I + 1) % 2] += t / 2 * I;
                }
                m1 += a[0][0] * a[1][0] + a[0][1] * a[1][1];
                m2 += a[0][0] * a[1][1] + a[0][1] * a[1][0];
            }
            ll pas = 0;
            pas = n * n - m1 - (s2 - m2);
            ans = min (ans, pas);
            pas = n * n - m2 - (s1 - m1);
            ans = min (ans, pas);
        }
    cout<<ans<<endl;
    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