Submission #90889

#	Time	Username	Problem	Language	Result	Execution time	Memory
90889		toloraia	Chessboard (IZhO18_chessboard)	C++17	0 / 100	28 ms	2856 KiB

chessboard

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

const int N = 1e5 + 5;

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

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

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