#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#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;
ll x1[ 100111 ], x2[ 100111 ];
ll y11[ 100111 ], y2[ 100111 ], ans = inf2;
vector < ll > divv;
map < ll , ll > mp;
ll white_first(ll sz, ll n, ll m){
ll sqrs = n / sz;
ll 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(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll n, m;
cin >> n >> m;
for(int i = 1; i <= m; i ++){
scanf("%lld%lld%lld%lld", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
}
divv.pb(1);
for(int i = 2; i <= ((ll)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";
}
cout << ans;
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:308:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
308 | for(int i = 0; i < divv.size(); i ++){
| ~~^~~~~~~~~~~~~
chessboard.cpp:291:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
291 | scanf("%lld%lld%lld%lld", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2025 ms |
3704 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2025 ms |
3704 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Execution timed out |
2025 ms |
3704 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
