#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#define ll long long int
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
ll inf2 = 3e18;
int x1[ 100111 ], x2[ 100111 ];
int y11[ 100111 ], y2[ 100111 ];
ll ans = inf2;
vector < int > divv;
map < int , int > mp;
int white_first(int sz, int n, int m){
int sqrs = n / sz;
int cnt_move = (sqrs & 1) ? ((((sqrs >> 1) * ((sqrs >> 1) + 1)) << 1) * (sz * sz)) : (sqrs >> 1) * (sqrs) * (sz * sz);
// cout << "w: " << cnt_move << " sz: " << sz << "\n";
for(int i = 1; i <= m; i ++){
if(x1[ i ] == x2[ i ] && y11[ i ] == y2[ i ]){
if(((x1[ i ] + sz - 1) / sz) & 1)
if(((y11[ i ] + sz - 1) / sz) & 1)
cnt_move ++;
else
cnt_move --;
else
if(((y11[ i ] + sz - 1) / sz) & 1)
cnt_move --;
else
cnt_move ++;
continue;
}
for(int j = 1, j2 = 1; j <= n; j += sz, j2 ++){
if(j <= x1[ i ] && x2[ i ] <= (j2 * sz)){
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
// break;
}
}
}else if(j <= x1[ i ] && x1[ i ] <= (j2 * sz) && (j2 * sz) <= x2[ i ]){
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
else
cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
// break;
}
}
}else if(x1[ i ] <= j && (j2 * sz) <= x2[ i ]){
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
else
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
else
cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
// break;
}
}
}else{
for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){
if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
break;
}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
else
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
else
cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
}else{
if(j2 & 1)
if(k2 & 1)
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
else
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
else
if(k2 & 1)
cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
else
cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
// break;
}
}
}
}
}
return cnt_move;
}
int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i ++){
scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
}
divv.pb(1);
for(int i = 2; i <= ((int)ceil(sqrt(n))); i ++){
if(n % i == 0 && !mp[ i ] && i != n){
divv.pb(i);
mp[ i ] ++;
if(!mp[ n / i ]){
divv.pb(n / i);
mp[ n / i ] ++;
}
}
}
// sort(all(divv));
for(int i = 0; i < divv.size(); i ++){
ll white = white_first(divv[ i ], n, m);
ans = min(ans, min((n * n) - white, white));
// cout << white << " " << (n * n) - white << "\n";
}
printf("%lld", ans);
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:295:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
295 | for(int i = 0; i < divv.size(); i ++){
| ~~^~~~~~~~~~~~~
chessboard.cpp:278:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
278 | scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
15 ms |
648 KB |
Output is correct |
| 17 |
Correct |
23 ms |
1608 KB |
Output is correct |
| 18 |
Correct |
30 ms |
1836 KB |
Output is correct |
| 19 |
Correct |
63 ms |
1664 KB |
Output is correct |
| 20 |
Correct |
82 ms |
1832 KB |
Output is correct |
| 21 |
Correct |
22 ms |
1476 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
17 ms |
896 KB |
Output is correct |
| 24 |
Correct |
29 ms |
1576 KB |
Output is correct |
| 25 |
Correct |
4 ms |
436 KB |
Output is correct |
| 26 |
Correct |
20 ms |
1156 KB |
Output is correct |
| 27 |
Correct |
24 ms |
1356 KB |
Output is correct |
| 28 |
Correct |
35 ms |
1664 KB |
Output is correct |
| 29 |
Correct |
10 ms |
716 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
20 ms |
1176 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
