#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 1001000
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;
long long n, k, xx1[N], xx2[N], xy1[N], xy2[N];
long long solve(int l, int color) {// color = 0 -> Top-left is black
long long ans = ((1ll * (n / l) * (n / l) + 1 - color) / 2) * l * l ;
REP(i, k) {
if (color ^ ((xx1[i] / l) % 2) == (xy1[i] / l) % 2) ans--;
else ans++;
}
return ans;
}
int main() {
#ifdef NERO
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
clock_t stime = clock();
#endif //NERO
IO;
cin >> n >> k;
long long ans = 1e9;
REP(i, k) cin >> xx1[i] >> xy1[i] >> xx2[i] >> xy2[i];
REP(i, k) xx1[i]--,xx2[i]--,xy1[i]--,xy2[i]--;
FOR(i, 1, sqrt(n)) if (n % i == 0) {
ans = min(ans, solve(i, 0));
ans = min(ans, solve(i, 1));
}
cout << ans;
#ifdef NERO
clock_t etime = clock();
cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.";
#endif // NERO
}
Compilation message
chessboard.cpp: In function 'long long int solve(int, int)':
chessboard.cpp:19:40: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
if (color ^ ((xx1[i] / l) % 2) == (xy1[i] / l) % 2) ans--;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
51 ms |
3868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
3868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
3868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
51 ms |
3868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |