#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#define int ll
const int MAX_N = 300010;
int n, k;
vector<tuple<int,int,int,int>> subr;
ll calgood(int w, int x1, int y1, int x2, int y2) {
// {
// ll res = 0;
// for (int i = x1;i <= x2;++i)
// for (int j = y1;j <= y2;++j) {
// int need = (1^(i/w) ^ (j/w))&1;
// res += need;
// }
// return res;
// }
ll res = 0;
ll a = 0, b = 0, c = 0, d = 0;
auto cal = [&](int l, int r, int ot) -> pair<ll,ll> {
ll a = 0, b = 0;
for (int i = l;i <= r;++i)
if ((1^(i/w)^ot&1))
++a;
else
++b;
return {a, b};
};
tie(a, b) = cal(x1, x2, y1/w);
tie(c, d) = cal(y1, y2, y1/w);
return a * c + b * d;
for (int i = y1;i <= y2;++i) {
if ((y1/w&1) == (i/w&1))
++c;
else
++d;
}
return a * c + b * d;
}
ll calcost(int wid) {
ll res = calgood(wid, 0, 0, n-1, n-1);
for (auto [x1, y1, x2, y2] : subr) {
ll area = 1ll * (x2-x1+1) * (y2-y1+1);
ll good = calgood(wid, x1, y1, x2, y2);
ll bad = area - good;
res -= good;
res += bad;
}
return min(res, 1ll * n * n - res);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
DE(n, k);
//if (n > 1000) return -1;
subr.resize(k);
for (auto &[x1, y1, x2, y2] : subr)
cin >> x1 >> y1 >> x2 >> y2, --x1, --x2, --y1, --y2;
ll res = 1ll * n * n;
for (int i = 1;i < n;++i)
if (n % i == 0)
chmin(res, calcost(i));
cout << res << '\n';
}
Compilation message
chessboard.cpp: In lambda function:
chessboard.cpp:43:19: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
43 | if ((1^(i/w)^ot&1))
| ~~^~
chessboard.cpp: In function 'll calgood(ll, ll, ll, ll, ll)':
chessboard.cpp:37:5: warning: unused variable 'res' [-Wunused-variable]
37 | ll res = 0;
| ^~~
chessboard.cpp: In function 'int32_t main()':
chessboard.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
chessboard.cpp:80:2: note: in expansion of macro 'DE'
80 | DE(n, k);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
2284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
2284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
