#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
#define f first
#define s second
#define int ll
using namespace std;
using ll = long long;
ll calc(pair<pair<int, int>, pair<int, int>> rec, int d, int par) {
auto p = rec;
if (p.f.f > p.s.f || p.f.s > p.s.s) {
return 0;
}
int x1 = p.f.f/d;
int x2 = p.s.f/d;
int y1 = p.f.s/d;
int y2 = p.s.s/d;
if (p.f.f%d == 0 && p.f.s%d == 0 && p.s.f%d == d-1 && p.s.s%d == d-1) {
int tot = (x2 - x1 + 1) * (y2 - y1 + 1);
if ((x1 + y1)%2 == par) {
//top left here is white
return (((x2 - x1 + 1)*(y2 - y1 + 1) + 1)/2)*d*d;
}
else {
return (tot - ((x2 - x1 + 1)*(y2 - y1 + 1) + 1)/2)*d*d;
}
}
else if (p.f.f%d == 0 && p.s.f%d == d-1 && y1 == y2) {
int tot = (x2 - x1 + 1);
if ((x1 + y1)%2 == par) {
return (tot + 1)/2 * (p.s.s - p.f.s + 1) * d;
}
else {
return (tot - (tot + 1)/2) * (p.s.s - p.f.s + 1) * d;
}
}
else if (p.f.s%d == 0 && p.s.s%d == d-1 && x1 == x2) {
int tot = (y2 - y1 + 1);
if ((x1 + y1)%2 == par) {
return (tot + 1)/2 * (p.s.f - p.f.f + 1)*d;
}
else {
return (tot - (tot + 1)/2) * (p.s.f - p.f.f + 1)*d;
}
}
else if (x1 == x2 && y1 == y2) {
if ((x1 + y1)%2 == par) {
return (p.s.f - p.f.f + 1) * (p.s.s - p.f.s + 1);
}
else {
return 0;
}
}
else if (x1 == x2) {
auto left = rec;
left.s.s = y1*d+d-1;
auto right = rec;
right.f.s = y2*d;
rec.f.s = left.s.s+1;
rec.s.s = right.f.s-1;
return calc(left, d, par) + calc(right, d, par) + calc(rec, d, par);
}
else if (y1 == y2) {
auto top = rec;
top.s.f = x1*d + d - 1;
auto bot = rec;
bot.f.f = x2*d;
rec.f.f = top.s.f+1;
rec.s.f = bot.f.f-1;
return calc(top, d, par) + calc(bot, d, par) + calc(rec, d, par);
}
else {
auto tleft = rec;
auto bleft = rec;
auto tright = rec;
auto bright = rec;
tleft.s.s = y1*d + d-1;
tleft.s.f = x1*d + d-1;
bleft.f.f = x2*d;
bleft.s.s = y1*d + d-1;
tright.f.s = y2*d;
tright.s.f = x1*d + d-1;
bright.f.f = x2*d;
bright.f.s = y2*d;
auto left = rec;
auto right = rec;
auto bot = rec;
auto top = rec;
left.f.f = tleft.s.f+1;
left.f.s = bleft.f.s-1;
left.s.s= y1*d + d-1;
right.f.f = tright.s.f+1;
right.s.f = bright.f.s-1;
right.f.s=y2*d;
bot.f.s = bleft.s.s+1;
bot.s.s=bright.f.s-1;
bot.f.f=x2*d;
top.f.s=tleft.s.s+1;
top.s.s=tright.f.s-1;
top.s.f=x1*d+d-1;
rec.f.f = d*(x1 + 1);
rec.f.s = d*(y1 + 1);
rec.s.f = d*x2-1;
rec.s.s = d*y2-1;
return calc(tleft, d, par) + calc(bleft, d, par) + calc(tright, d, par) + calc(bright, d, par) + calc(left, d, par) + calc(right, d, par) + calc(bot, d, par) + calc(top, d, par) + calc(rec, d, par);
}
}
signed main() {
cin.tie(0);
cin.sync_with_stdio(0);
int N, K;
cin >> N >> K;
vector<pair<pair<int, int>, pair<int, int>>> vec(K);
for (int i = 0; i < K; i++) {
cin >> vec[i].f.f >> vec[i].f.s >> vec[i].s.f >> vec[i].s.s;
vec[i].f.f--;
vec[i].f.s--;
vec[i].s.f--;
vec[i].s.s--;
}
int ans = N*N;
for (int d = 1; d < N; d++) {
if (N%d == 0) {
int cnt = N/d;
// ll white;
// ll black;
int black = d*d*((cnt * cnt)+1)/2;
int white = d*d*(cnt*cnt - ((cnt*cnt)+1)/2);
for (auto& p : vec) {
int tot = (p.s.f - p.f.f + 1) * (p.s.s - p.f.s + 1);
int res1 = calc(p, d, 0);
int res2 = calc(p, d, 1);
black += res2;
black -= tot-res2;
white += res1;
white -= tot-res1;
}
ans = min({ans, white, black});
//top left is black
}
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
2284 KB |
Output is correct |
2 |
Correct |
8 ms |
876 KB |
Output is correct |
3 |
Correct |
21 ms |
1516 KB |
Output is correct |
4 |
Correct |
23 ms |
1772 KB |
Output is correct |
5 |
Correct |
30 ms |
2028 KB |
Output is correct |
6 |
Correct |
18 ms |
1388 KB |
Output is correct |
7 |
Correct |
4 ms |
620 KB |
Output is correct |
8 |
Correct |
18 ms |
1388 KB |
Output is correct |
9 |
Correct |
40 ms |
3180 KB |
Output is correct |
10 |
Correct |
27 ms |
1900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
14 ms |
1132 KB |
Output is correct |
17 |
Correct |
31 ms |
2924 KB |
Output is correct |
18 |
Correct |
47 ms |
3436 KB |
Output is correct |
19 |
Correct |
152 ms |
3052 KB |
Output is correct |
20 |
Correct |
173 ms |
3436 KB |
Output is correct |
21 |
Correct |
32 ms |
2924 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
31 ms |
1644 KB |
Output is correct |
24 |
Correct |
43 ms |
3180 KB |
Output is correct |
25 |
Correct |
6 ms |
620 KB |
Output is correct |
26 |
Correct |
27 ms |
2156 KB |
Output is correct |
27 |
Correct |
41 ms |
2432 KB |
Output is correct |
28 |
Correct |
46 ms |
3308 KB |
Output is correct |
29 |
Correct |
15 ms |
1388 KB |
Output is correct |
30 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
2284 KB |
Output is correct |
2 |
Correct |
8 ms |
876 KB |
Output is correct |
3 |
Correct |
21 ms |
1516 KB |
Output is correct |
4 |
Correct |
23 ms |
1772 KB |
Output is correct |
5 |
Correct |
30 ms |
2028 KB |
Output is correct |
6 |
Correct |
18 ms |
1388 KB |
Output is correct |
7 |
Correct |
4 ms |
620 KB |
Output is correct |
8 |
Correct |
18 ms |
1388 KB |
Output is correct |
9 |
Correct |
40 ms |
3180 KB |
Output is correct |
10 |
Correct |
27 ms |
1900 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
14 ms |
1132 KB |
Output is correct |
27 |
Correct |
31 ms |
2924 KB |
Output is correct |
28 |
Correct |
47 ms |
3436 KB |
Output is correct |
29 |
Correct |
152 ms |
3052 KB |
Output is correct |
30 |
Correct |
173 ms |
3436 KB |
Output is correct |
31 |
Correct |
32 ms |
2924 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
31 ms |
1644 KB |
Output is correct |
34 |
Correct |
43 ms |
3180 KB |
Output is correct |
35 |
Correct |
6 ms |
620 KB |
Output is correct |
36 |
Correct |
27 ms |
2156 KB |
Output is correct |
37 |
Correct |
41 ms |
2432 KB |
Output is correct |
38 |
Correct |
46 ms |
3308 KB |
Output is correct |
39 |
Correct |
15 ms |
1388 KB |
Output is correct |
40 |
Correct |
2 ms |
364 KB |
Output is correct |
41 |
Correct |
139 ms |
2924 KB |
Output is correct |
42 |
Correct |
57 ms |
3308 KB |
Output is correct |
43 |
Correct |
83 ms |
2924 KB |
Output is correct |
44 |
Correct |
51 ms |
3180 KB |
Output is correct |
45 |
Correct |
44 ms |
3436 KB |
Output is correct |
46 |
Correct |
156 ms |
3180 KB |
Output is correct |
47 |
Correct |
37 ms |
3052 KB |
Output is correct |
48 |
Correct |
67 ms |
3052 KB |
Output is correct |
49 |
Correct |
46 ms |
2924 KB |
Output is correct |
50 |
Correct |
681 ms |
3180 KB |
Output is correct |
51 |
Correct |
720 ms |
3308 KB |
Output is correct |
52 |
Correct |
678 ms |
3180 KB |
Output is correct |
53 |
Correct |
738 ms |
3436 KB |
Output is correct |
54 |
Correct |
673 ms |
3052 KB |
Output is correct |
55 |
Correct |
742 ms |
3436 KB |
Output is correct |
56 |
Correct |
643 ms |
3052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
Correct |
31 ms |
2284 KB |
Output is correct |
10 |
Correct |
8 ms |
876 KB |
Output is correct |
11 |
Correct |
21 ms |
1516 KB |
Output is correct |
12 |
Correct |
23 ms |
1772 KB |
Output is correct |
13 |
Correct |
30 ms |
2028 KB |
Output is correct |
14 |
Correct |
18 ms |
1388 KB |
Output is correct |
15 |
Correct |
4 ms |
620 KB |
Output is correct |
16 |
Correct |
18 ms |
1388 KB |
Output is correct |
17 |
Correct |
40 ms |
3180 KB |
Output is correct |
18 |
Correct |
27 ms |
1900 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
14 ms |
1132 KB |
Output is correct |
35 |
Correct |
31 ms |
2924 KB |
Output is correct |
36 |
Correct |
47 ms |
3436 KB |
Output is correct |
37 |
Correct |
152 ms |
3052 KB |
Output is correct |
38 |
Correct |
173 ms |
3436 KB |
Output is correct |
39 |
Correct |
32 ms |
2924 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
31 ms |
1644 KB |
Output is correct |
42 |
Correct |
43 ms |
3180 KB |
Output is correct |
43 |
Correct |
6 ms |
620 KB |
Output is correct |
44 |
Correct |
27 ms |
2156 KB |
Output is correct |
45 |
Correct |
41 ms |
2432 KB |
Output is correct |
46 |
Correct |
46 ms |
3308 KB |
Output is correct |
47 |
Correct |
15 ms |
1388 KB |
Output is correct |
48 |
Correct |
2 ms |
364 KB |
Output is correct |
49 |
Correct |
139 ms |
2924 KB |
Output is correct |
50 |
Correct |
57 ms |
3308 KB |
Output is correct |
51 |
Correct |
83 ms |
2924 KB |
Output is correct |
52 |
Correct |
51 ms |
3180 KB |
Output is correct |
53 |
Correct |
44 ms |
3436 KB |
Output is correct |
54 |
Correct |
156 ms |
3180 KB |
Output is correct |
55 |
Correct |
37 ms |
3052 KB |
Output is correct |
56 |
Correct |
67 ms |
3052 KB |
Output is correct |
57 |
Correct |
46 ms |
2924 KB |
Output is correct |
58 |
Correct |
681 ms |
3180 KB |
Output is correct |
59 |
Correct |
720 ms |
3308 KB |
Output is correct |
60 |
Correct |
678 ms |
3180 KB |
Output is correct |
61 |
Correct |
738 ms |
3436 KB |
Output is correct |
62 |
Correct |
673 ms |
3052 KB |
Output is correct |
63 |
Correct |
742 ms |
3436 KB |
Output is correct |
64 |
Correct |
643 ms |
3052 KB |
Output is correct |
65 |
Correct |
1 ms |
364 KB |
Output is correct |
66 |
Correct |
1 ms |
364 KB |
Output is correct |
67 |
Incorrect |
1230 ms |
5484 KB |
Output isn't correct |
68 |
Halted |
0 ms |
0 KB |
- |