This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ll long long
struct rect{ int x1, y1, x2, y2; };
ll n, k, ans = 1e18; vector<rect> A;
void solve(ll sz, int T){
ll bl = (n / sz) * (n / sz) / 2;
if ((n / sz) % 2) bl += T;
ll res = sz * sz * bl;
auto eval = [&](int x1, int y1, int x2, int y2, ll area){
int dX = x2 - x1 + 1;
int dY = y2 - y1 + 1;
if (!dX or !dY) return 0LL;
ll L = (dY - 1) / sz + 1; //ceil div to take care of smoll square
ll H = (dX - 1) / sz + 1;
ll black = L * H / 2;
//odd x odd dimension will have one extra of white/black
int a = (x1 / sz) % 2, b = (y1 / sz) % 2;
if (L % 2 and H % 2) black += (a ^ b ^ T); //T = 1 means start is black
ll white = L * H - black;
return black * area - white * area; //color operations saved
};
for (auto [x1, y1, x2, y2] : A){
ll VU = sz - (x1 % sz);
ll VD = (x2 % sz) + 1;
ll HL = sz - (y1 % sz);
ll HR = (y2 % sz) + 1;
//small dimension cases
if (VU + VD > x2 - x1 + 1) VU = x2 - x1 + 1, VD = 0;
if (HL + HR > y2 - y1 + 1) HL = y2 - y1 + 1, HR = 0;
//inner rect
res -= eval(x1 + VU, y1 + HL, x2 - VD, y2 - HR, (ll)sz * sz);
//corner rec
res -= eval(x1, y1, x1 + VU - 1, y1 + HL - 1, HL * VU); //top left
res -= eval(x2 - VD + 1, y1, x2, y1 + HL - 1, VD * HL); //bottom left
res -= eval(x1, y2 - HR + 1, x1 + VU - 1, y2, HR * VU); //top right
res -= eval(x2 - VD + 1, y2 - HR + 1, x2, y2, VD * HR); //bottom right
//side rec
res -= eval(x1 + VU, y1, x2 - VD, y1 + HL - 1, sz * HL); //left
res -= eval(x1, y1 + HL, x1 + VU - 1, y2 - HR, sz * VU); //up
res -= eval(x1 + VU, y2 - HR + 1, x2 - VD, y2, sz * HR); //right
res -= eval(x2 - VD + 1, y1 + HL, x2, y2 - HR, sz * VD); //down
}
ans = min(ans, res);
}
int main(){
cin >> n >> k; A.resize(k);
for (auto &i : A){
cin >> i.x1 >> i.y1 >> i.x2 >> i.y2;
i.x1--; i.y1--; i.x2--; i.y2--; //0 indexed makes mod ops easier
}
FOR(i, 2, n + 1) if (!(n % i)) solve(n / i, 0), solve(n / i, 1);
cout<<ans<<endl;
}
Compilation message (stderr)
chessboard.cpp: In function 'void solve(long long int, int)':
chessboard.cpp:34:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for (auto [x1, y1, x2, y2] : A){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |