Submission #91746

#	Time	Username	Problem	Language	Result	Execution time	Memory
91746		popovicirobert	Chessboard (IZhO18_chessboard)	C++14	100 / 100	406 ms	4380 KiB

chessboard

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;

struct Data {
    int x1, y1, x2, y2;
}arr[MAXN + 1];

inline void add(vector <ll> &fr, ll a, ll b) {
    fr[0] += a;
    fr[1] += b;
}

inline int get(int x, int len) {
    if(x - len + 1 < 0) {
        return -1;
    }
    return ((x - len + 1) / len) * len + len - 1;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for(i = 1; i <= k; i++) {
        cin >> arr[i].x1 >> arr[i].y1 >> arr[i].x2 >> arr[i].y2;
        arr[i].x1--, arr[i].y1--;
        arr[i].x2--, arr[i].y2--;
    }
    ll ans = 1LL * n * n;
    for(int len = 1; len < n; len++) {
        if(n % len == 0) {
            vector <ll> fr(2);
            for(i = 1; i <= k; i++) {
                if(arr[i].x2 / len == arr[i].x1 / len && arr[i].y2 / len == arr[i].y1 / len) {
                    if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
                        fr[0] += 1LL * (arr[i].x2 - arr[i].x1 + 1) * (arr[i].y2 - arr[i].y1 + 1);
                    }
                    else {
                        fr[1] += 1LL * (arr[i].x2 - arr[i].x1 + 1) * (arr[i].y2 - arr[i].y1 + 1);
                    }
                    continue;
                }
                int a = ((arr[i].x1 + len - 1) / len) * len - arr[i].x1;
                int A = ((arr[i].y1 + len - 1) / len) * len - arr[i].y1;
                int b = arr[i].x2 - get(arr[i].x2, len);
                int B = arr[i].y2 - get(arr[i].y2, len);
                if(arr[i].y2 / len == arr[i].y1 / len) {
                    if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
                        add(fr, 1LL * a * (arr[i].y2 - arr[i].y1 + 1), 0);
                    }
                    else {
                        add(fr, 0, 1LL * a * (arr[i].y2 - arr[i].y1 + 1));
                    }
                    if(((arr[i].x1 + a) / len + arr[i].y1 / len) % 2 == 0) {
                        int cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
                        add(fr, 1LL * len * ((cur + 1) / 2) * (arr[i].y2 - arr[i].y1 + 1), 1LL * len * (cur / 2) * (arr[i].y2 - arr[i].y1 + 1));
                    }
                    else {
                        int cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
                        add(fr, 1LL * len * (cur / 2) * (arr[i].y2 - arr[i].y1 + 1), 1LL * len * ((cur + 1) / 2) * (arr[i].y2 - arr[i].y1 + 1));
                    }
                    if((arr[i].x2 / len + arr[i].y1 / len) % 2 == 0) {
                        add(fr, 1LL * b * (arr[i].y2 - arr[i].y1 + 1), 0);
                    }
                    else {
                        add(fr, 0, 1LL * b * (arr[i].y2 - arr[i].y1 + 1));
                    }
                    continue;
                }
                if(arr[i].x2 / len == arr[i].x1 / len) {
                    if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
                        add(fr, 1LL * A * (arr[i].x2 - arr[i].x1 + 1), 0);
                    }
                    else {
                        add(fr, 0, 1LL * A * (arr[i].x2 - arr[i].x1 + 1));
                    }
                    if(((arr[i].y1 + A) / len + arr[i].x1 / len) % 2 == 0) {
                        int cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
                        add(fr, 1LL * len * ((cur + 1) / 2) * (arr[i].x2 - arr[i].x1 + 1), 1LL * len * (cur / 2) * (arr[i].x2 - arr[i].x1 + 1));
                    }
                    else {
                        int cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
                        add(fr, 1LL * len * (cur / 2) * (arr[i].x2 - arr[i].x1 + 1), 1LL * len * ((cur + 1) / 2) * (arr[i].x2 - arr[i].x1 + 1));
                    }
                    if((arr[i].x1 / len + arr[i].y2 / len) % 2 == 0) {
                        add(fr, 1LL * B * (arr[i].x2 - arr[i].x1 + 1), 0);
                    }
                    else {
                        add(fr, 0, 1LL * B * (arr[i].x2 - arr[i].x1 + 1));
                    }
                    continue;
                }
                /*if(len == 2) {
                    cerr << a << " " << A << " " << b << " " << B << "\n";
                }*/

                if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
                    add(fr, 1LL * a * A, 0);
                }
                else {
                    add(fr, 0, 1LL * a * A);
                }
                int cur;
                if((arr[i].x1 / len + (arr[i].y1 + A) / len) % 2 == 1) {
                    cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
                    add(fr, 1LL * len * (cur / 2) * a, 1LL * len * ((cur + 1) / 2) * a);
                }
                else {
                    cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
                    add(fr, 1LL * len * ((cur + 1) / 2) * a, 1LL * len * (cur / 2) * a);
                }
                if(((arr[i].x1 + a) / len + arr[i].y1 / len) % 2 == 1) {
                    cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
                    add(fr, 1LL * len * (cur / 2) * A, 1LL * len * ((cur + 1) / 2) * A);
                }
                else {
                    cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
                    add(fr, 1LL * len * ((cur + 1) / 2) * A, 1LL * len * (cur / 2) * A);
                }

                //////////////////////////////////
                if((arr[i].x1 / len + arr[i].y2 / len) % 2 == 0) {
                    add(fr, 1LL * a * B, 0);
                }
                else {
                    add(fr, 0, 1LL * a * B);
                }
                if((arr[i].x2 / len + arr[i].y1 / len) % 2 == 0) {
                    add(fr, 1LL * b * A, 0);
                }
                else {
                    add(fr, 0, 1LL * b * A);
                }

                //////////////////////////////////////
                if((arr[i].x2 / len + arr[i].y2 / len) % 2 == 0) {
                    add(fr, 1LL * b * B, 0);
                }
                else {
                    add(fr, 0, 1LL * b * B);
                }
                if(((arr[i].x2 - b) / len + arr[i].y2 / len) % 2 == 1) {
                    cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
                    add(fr, 1LL * len * (cur / 2) * B, 1LL * len * ((cur + 1) / 2) * B);
                }
                else {
                    cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
                    add(fr, 1LL * len * ((cur + 1) / 2) * B, 1LL * len * (cur / 2) * B);
                }
                if((arr[i].x2 / len + (arr[i].y2 - B) / len) % 2 == 1) {
                    cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
                    add(fr, 1LL * len * (cur / 2) * b, 1LL * len * ((cur + 1) / 2) * b);
                }
                else {
                    cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
                    add(fr, 1LL * len * ((cur + 1) / 2) * b, 1LL * len * (cur / 2) * b);
                }
                ///////////////////////////////

                ll cnt0, cnt1;
                ll s = 1LL * (arr[i].x2 - arr[i].x1 + 1 - a - b) * (arr[i].y2 - arr[i].y1 + 1 - A - B);
                if((s / (1LL * len * len)) % 2 == 0) {
                    cnt0 = cnt1 = (s / (1LL * len * len)) / 2;
                }
                else {
                    cnt0 = cnt1 = (s / (1LL * len * len)) / 2;
                    if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
                        cnt0++;
                    }
                    else {
                        cnt1++;
                    }
                }
                fr[0] += 1LL * len * len * cnt0;
                fr[1] += 1LL * len * len * cnt1;
            }
            ll cnt0, cnt1;
            if((n / len) % 2 == 0) {
                cnt0 = cnt1 = ((1LL * n * n) / (1LL * len * len)) / 2;
            }
            else {
                cnt0 = cnt1 = ((1LL * n * n) / (1LL * len * len)) / 2;
                cnt0++;
            }
            cnt0 *= 1LL * len * len;
            cnt1 *= 1LL * len * len;
            //cerr << len << " " << cnt0 << " " << cnt1 << " " << fr[0] << " " << fr[1] << "\n";
            ans = min(ans, min(cnt0 - fr[0] + fr[1], cnt1 - fr[1] + fr[0]));
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    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