#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 1e6 + 66;
#define y1 slkdjflkjsdlfkjlskjfjklkdjslfjslkdjflkjlsdkjflkjslkdjflkdslfkjsldklkjsdjfntnfj
#define y0 alsjdljrktnmndfdfgjhkjhdkfjgbtnmbmfhkjgdkjfhkjxhkjhgtgbhhdjbhjhtdbjbhjhtbhbgbb
int x0[N], y0[N], x1[N], y1[N], n, k;
ll cnt(int d, int x, int y) {
if (x < 0 || y < 0) return 0;
int X = x / d, Y = y / d;
//if (0) {
ll cur = 0;
for (int i = 0 ; i < X * d ; ++ i) {
for (int j = 0 ; j < Y * d ; ++ j) {
if ((i / d + j / d) % 2 == 0) cur++;
}
}
//return cur;
//}
cerr << d << " : " << x << " " << y << " " << X << " " << Y << endl;
//ll cur = (X * 1ll * Y + 1) / 2;
ll Xc = Y % 2 == 1 ? X / 2 : (X + 1) / 2;
ll Yc = X % 2 == 1 ? Y / 2 : (Y + 1) / 2;
cur += Xc * d * (y - Y * d + 1);
cur += Yc * d * (x - X * d + 1);
if ((X + Y) % 2 == 0)
cur += (x - X * d + 1) * 1ll * (y - Y * d + 1);
return cur;
}
ll solve(int d) {
ll cur = cnt(d, n-1, n-1);
for (int i = 0 ; i < k ; ++ i) {
ll black = cnt(d, x1[i], y1[i]) - cnt(d, x0[i] - 1, y1[i]) - cnt(d, x1[i], y0[i] - 1) + cnt(d, x0[i] - 1, y0[i] - 1);
ll area = (y1[i] - y0[i] + 1) * 1ll * (x1[i] - x0[i] + 1);
//cerr << d << " " << black << " " << area << " d/black/area\n";
cur += area - black * 2;
}
return cur;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 0 ; i < k ; ++ i) {
cin >> x0[i] >> y0[i] >> x1[i] >> y1[i];
x0[i]--, y0[i]--, x1[i]--, y1[i]--;
}
ll ans = n * 1ll * n;
for (int d = 1 ; d < n ; ++ d) {
if (n % d == 0) {
for (int i = 0 ; i < n ; ++ i) {
for (int j = 0 ; j < n ; ++ j) {
if ((i / d + j / d) % 2 == 0) cerr << "X";
else cerr << ".";
}
cerr << "\n";
}
cerr << "\n";
ll cur = solve(d);
ans = min(ans, min(cur, n * 1ll * n - cur));
}
}
cout << ans;
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:61:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
61 | if ((i / d + j / d) % 2 == 0) cerr << "X";
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2077 ms |
1516 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
428 KB |
Output is correct |
2 |
Correct |
7 ms |
364 KB |
Output is correct |
3 |
Correct |
47 ms |
364 KB |
Output is correct |
4 |
Correct |
168 ms |
492 KB |
Output is correct |
5 |
Correct |
70 ms |
568 KB |
Output is correct |
6 |
Correct |
47 ms |
364 KB |
Output is correct |
7 |
Correct |
93 ms |
364 KB |
Output is correct |
8 |
Correct |
59 ms |
364 KB |
Output is correct |
9 |
Correct |
43 ms |
364 KB |
Output is correct |
10 |
Correct |
4 ms |
364 KB |
Output is correct |
11 |
Correct |
38 ms |
364 KB |
Output is correct |
12 |
Correct |
9 ms |
364 KB |
Output is correct |
13 |
Correct |
101 ms |
492 KB |
Output is correct |
14 |
Correct |
109 ms |
364 KB |
Output is correct |
15 |
Correct |
35 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
428 KB |
Output is correct |
2 |
Correct |
7 ms |
364 KB |
Output is correct |
3 |
Correct |
47 ms |
364 KB |
Output is correct |
4 |
Correct |
168 ms |
492 KB |
Output is correct |
5 |
Correct |
70 ms |
568 KB |
Output is correct |
6 |
Correct |
47 ms |
364 KB |
Output is correct |
7 |
Correct |
93 ms |
364 KB |
Output is correct |
8 |
Correct |
59 ms |
364 KB |
Output is correct |
9 |
Correct |
43 ms |
364 KB |
Output is correct |
10 |
Correct |
4 ms |
364 KB |
Output is correct |
11 |
Correct |
38 ms |
364 KB |
Output is correct |
12 |
Correct |
9 ms |
364 KB |
Output is correct |
13 |
Correct |
101 ms |
492 KB |
Output is correct |
14 |
Correct |
109 ms |
364 KB |
Output is correct |
15 |
Correct |
35 ms |
364 KB |
Output is correct |
16 |
Execution timed out |
2087 ms |
768 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2077 ms |
1516 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Execution timed out |
2077 ms |
1516 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |