Submission #946060

#	Time	Username	Problem	Language	Result	Execution time	Memory
946060		atom	Chessboard (IZhO18_chessboard)	C++17	100 / 100	798 ms	10240 KiB

chessboard

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

#define int long long

vector <vector <int>> rect;
int n, m;
int res = 1e18;

int f(int x, int y, int k) {
    int cnt = 0;
    int _x = (x / k) * k, _y = (y / k) * k;
    if ((_x / k + _y / k) & 1) {
        cnt += ((_x / k) * (_y / k)) / 2 * (k * k);
        cnt += ((_y / k) + 1) / 2 * (x - _x) * k;
        cnt += ((_x / k) + 1) / 2 * (y - _y) * k;
    }
    else {
        cnt += ((_x / k) * (_y / k) + 1) / 2 * (k * k);
        cnt += ((_y / k)) / 2 * (x - _x) * k;
        cnt += ((_x / k)) / 2 * (y - _y) * k;
        cnt += (x - _x) * (y - _y);
    }
    return cnt;
}

void solve(int k) {
    int ans = (n * n - f(n, n, k));
    for (auto x : rect) {
        int x1 = x[0], y1 = x[1], x2 = x[2], y2 = x[3];
        int w = f(x2, y2, k) + f(x1 - 1, y1 - 1, k) - f(x2, y1 - 1, k) - f(x1 - 1, y2, k);
        ans += w;
        ans -= (x2 - x1 + 1) * (y2 - y1 + 1) - w; 
    }

    res = min({res, ans, n * n - ans});
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif
        
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rect.push_back({x1, y1, x2, y2});
    }

    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            solve(i);
            if (i != n / i && i > 1)
                solve(n / i); 
        }
    }
    cout << res << "\n";
}

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