#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
typedef long long ll;
#define int ll
#define y1 sda
const int N = 1e5 + 5;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
int n, k;
ll ans = INF, k_area;
vector < int > v;
ll get(int x, int y, int xx, int yy, int len) {
if (x > xx || y > yy)
return 0;
int f = ((x / len) % 2 == (y / len) % 2);
x = (xx - x + 1) / len;
y = (yy - y + 1) / len;
ll num = (x * y) / 2;
if (f) {
num += ((x * y) % 2);
}
return num * len * len;
}
ll get_corner(int x, int y, int xx, int yy, int len) {
if (x > xx || y > yy)
return 0;
int f = ((x / len) % 2) == ((y / len) % 2);
x = (xx - x + 1);
y = (yy - y + 1);
ll num = (x * y) * f;
return num;
}
int left(int l, int len) {
return ((l + (len - 1)) / len) * len;
}
int right(int r, int len) {
return (((r + 1) / len) * len) - 1;
}
ll get_sidex(int x, int y, int xx, int yy, int len) {
if (x > xx || y > yy)
return 0;
int f = ((x / len) % 2) == ((y / len) % 2);
y = yy - y + 1;
x = (xx - x + 1) / len;
ll num = (x / 2) + f * (x % 2);
return num * y * len;
}
ll get_sidey(int x, int y, int xx, int yy, int len) {
if (x > xx | y > yy)
return 0;
int f = ((x / len) % 2) == ((y / len) % 2);
y = (yy - y + 1) / len;
x = xx - x + 1;
ll num = (y / 2) + f * (y % 2);
return num * x * len;
}
ll get_one(int x, int y, int len) {
return (((x / len) % 2) == ((y / len) % 2));
}
int x1[N], y1[N], x2[N], y2[N];
main() {
cin >> n >> k;
for (int i = 1; i <= k; ++i) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i]--;
y1[i]--;
x2[i]--;
y2[i]--;
k_area += (y2[i] - y1[i] + 1) * (x2[i] - x1[i] + 1);
}
v.push_back(1);
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
v.push_back(i);
if (n / i != i) {
v.push_back(n / i);
}
}
}
cout << k_area << "\n";
for (int i : v) {
int m = n / i, cnt_black = 0, cnt_white = 0;
ll black = (((m * m) / 2) + ((m * m) % 2)) * (i * 1ll * i);
ll white = (n * 1ll * n) - black;
// cout << i << " " << m << " " << black << " " << white << "\n";
for (int j = 1; j <= k; ++j) {
if (x1[j] == x2[j] && y1[j] == y2[j]) {
cnt_black += get_one(x1[j], y1[j], i);
} else {
int px1 = -1, px2 = -1, py1 = -1, py2 = -1;
ll center_black = 0, corner_black = 0, side_black = 0;
px1 = left(x1[j], i);
py1 = left(y1[j], i);
px2 = right(x2[j], i);
py2 = right(y2[j], i);
center_black = get(px1, py1, px2, py2, i);
corner_black = get_corner(x1[j], y1[j], px1 - 1, py1 - 1, i) +
get_corner(px2 + 1, y1[j], x2[j], py1 - 1, i) +
get_corner(x1[j], py2 + 1, px1 - 1, y2[j], i) +
get_corner(px2 + 1, py2 + 1, x2[j], y2[j], i);
side_black = get_sidex(px1, y1[j], px2, py1 - 1, i) + get_sidex(px1, py2 + 1, px2, y2[j], i) +
get_sidey(x1[j], py1, px1 - 1, py2, i) + get_sidey(px2 + 1, py1, x2[j], py2, i);
cnt_black += center_black + corner_black + side_black;
}
}
cnt_white = k_area - cnt_black;
ll fx = (black - cnt_black) + cnt_white;
ll fy = (white - cnt_white) + cnt_black;
// cout << cnt_black << " " << cnt_white << " " << fx << " " << fy << "\n\n";
ans = min(ans, min(fx, fy));
}
cout << ans;
}
Compilation message
chessboard.cpp: In function 'll get_sidey(ll, ll, ll, ll, ll)':
chessboard.cpp:66:11: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
if (x > xx | y > yy)
~~^~~~
chessboard.cpp: At global scope:
chessboard.cpp:81:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
2404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
2404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
