Submission #1132050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132050		_DaNeK_	Chessboard (IZhO18_chessboard)	C++20	70 / 100	376 ms	428 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define bust ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
const int INF = (ll) 1e9 + 10;
const int N = 1e5 + 44;
const int LOG = 20;
const int SZ = 1000;
const int mod = 1e9 + 7;
const ld eps = 1e-12;

vector<int> divs;
ll cnt[N];

void add (int x1, int y1, int x2, int y2, int d, ll &cntb, ll &cntw) {
    //cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
    if (x1 > x2 || y1 > y2) return ;
    int col = (x1 / d + y1 / d) % 2;
    if (col) cntw += (y2 - y1 + 1) * 1ll * (x2 - x1 + 1);
    else cntb += (y2 - y1 + 1) * 1ll * (x2 - x1 + 1);
    return ;
}

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        if (n % i == 0)
            divs.pb(i);
    }
    int m = divs.size();
    for (int i = 0; i < m; ++i) {
        ll tmp = n / divs[i];
        cnt[2 * i] = tmp * (tmp / 2) + (tmp % 2 ? tmp / 2 + 1 : 0);
        cnt[2 * i + 1] = tmp * 1ll * tmp - cnt[2 * i];
        cnt[2 * i] *= divs[i] * 1ll * divs[i];
        cnt[2 * i + 1] *= divs[i] * 1ll * divs[i];
        //cout << cnt[2 * i] << " " << cnt[2 * i + 1] << " ";
    }
    for (int i = 0; i < k; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        --x1, --y1, --x2, --y2;
        for (int i = 0; i < m; ++i) {
            ll cntb = 0, cntw = 0, d = divs[i];
            if (x1 / d == x2 / d && y1 / d == y2 / d) {
                add(x1, y1, x2, y2, d, cntb, cntw);
                cnt[2 * i] += cntw - cntb;
                cnt[2 * i + 1] += cntb - cntw;
                continue ;
            }
            ll stx = (x1 + d - 1) / d, lstx = (x2 + 1) / d - 1;
            // on [st, ..., lstx] we have full squares
            ll sty = (y1 + d - 1) / d, lsty = (y2 + 1) / d - 1;
            // on [sty, ..., lsty] we have full squares
            ll l = lstx - stx + 1, w = lsty - sty + 1;
            //cout << stx << " " << sty << " " << lstx << " " << lsty << "\n";
            if (lstx >= stx && lsty >= sty) {
                cntb = l * (w / 2) + (w % 2 ? l / 2 + 1 : 0);
                cntw = l * w - cntb;
                cntb *= d * d;
                cntw *= d * d;
                // check what colour (stx, sty) has
                if ((stx + sty) % 2 != 0) swap(cntb, cntw);
            }
            //cout << d << " " << cntb << " " << cntw << "\n";
            if (lstx >= stx) {
                ll addb = 0, addw = 0;
                addb = (l + 1) / 2;
                addw = l - addb;
                addb *= d;
                addw *= d;
                // left part
                if ((stx + (sty - 1)) % 2 != 0) {
                    cntb += addw * (sty * d - y1);
                    cntw += addb * (sty * d - y1);
                }
                else {
                    cntb += addb * (sty * d - y1);
                    cntw += addw * (sty * d - y1);
                }
                // right part
                if ((stx + lsty + 1) % 2 != 0) {
                    cntb += addw * (y2 - lsty * d - d + 1);
                    cntw += addb * (y2 - lsty * d - d + 1);
                    //cout << addw * (y2 - lsty * d - d + 1) << " " << addb * (y2 - lsty * d - d + 1) << " fff \n";
                }
                else {
                    cntb += addb * (y2 - lsty * d - d + 1);
                    cntw += addw * (y2 - lsty * d - d + 1);
                    //cout << addw * (y2 - lsty * d - d) << " " << addb * (y2 - lsty * d - d) << " ddd\n";
                }
            }
            if (lsty >= sty) {
                ll addb = 0, addw = 0;
                addb = (w + 1) / 2;
                addw = w - addb;
                addb *= d;
                addw *= d;
                //cout << addb << " " << addw << "\n";
                // up part
                if ((stx - 1 + sty) % 2 != 0) {
                    cntb += addw * (stx * d - x1);
                    cntw += addb * (stx * d - x1);
                }
                else {
                    cntb += addb * (stx * d - x1);
                    cntw += addw * (stx * d - x1);
                }
                // down part
                if ((lstx + 1 + sty) % 2 != 0) {
                    cntb += addw * (x2 - lstx * d - d + 1);
                    cntw += addb * (x2 - lstx * d - d + 1);
                }
                else {
                    cntb += addb * (x2 - lstx * d - d + 1);
                    cntw += addw * (x2 - lstx * d - d + 1);
                }
            }
            //if (lstx < stx && lsty < sty) {
                //add(x1, y1, x2, y2, d, cntb, cntw);
            //}
            //else {
                // 4 corners
                //cout << d << " " << cntb << " " << cntw << "\n";
                //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << stx * d - 1 << " " << sty * d - 1 << " " << lstx * d + d << " " << lsty * d + d << "\n";
                add(x1, y1, stx * d - 1, sty * d - 1, d, cntb, cntw);
                add(x1, lsty * d + d, stx * d - 1, y2, d, cntb, cntw);
                add(lstx * d + d, y1, x2, sty * d - 1, d, cntb, cntw);
                add(lstx * d + d, lsty * d + d, x2, y2, d, cntb, cntw);
            //}
            //cout << d << " " << cntb << " " << cntw << "\n";
            cnt[2 * i] += cntw - cntb;
            cnt[2 * i + 1] += cntb - cntw;
        }
        //cout << "\n";
    }
    ll ans = n * 1ll * n;
    for (int i = 0; i < 2 * m; ++i) ans = min(ans, cnt[i]);
    cout << ans << "\n";
    return ;
}

/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/


int main()
{
    //freopen ("input-slotmachine-c952.txt", "r", stdin);
    //freopen ("output.txt", "w", stdout);
    //bust
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
        //cout << "Case #" << i << ": ";
        solve ();
    }
    return 0;
}

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