#include <iostream>
#include <vector>
#define int long long
using namespace std;
int a[1005][1005];
int spw[1005][1005], spb[1005][1005];
int x1[100005], x2[100005], y1[100005], y2[100005];
void add(int x, int y, int val, int &s1, int &s2)
{
if((int)(x + y) % 2 == 0)
s1 += val;
else
s2 += val;
return;
}
signed main()
{
int s1 = 0, s2 = 0;
int n, k;
cin>>n>>k;
vector<int> divs;
for(int i = 1; i * i <= n; i++)
if(n % i == 0)
{
divs.push_back(i);
if(i * i != n && i != 1)
divs.push_back(n / i);
}
for(int i = 1; i <= k; i++)
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
int minn = n * n;
for(auto d : divs)
{
int s1 = 0, s2 = 0;
for(int i = 1; i <= k; i++)
{
int cx1 = (int)(x1[i] - 1) / d + 1;
int cy1 = (int)(y1[i] - 1) / d + 1;
int cx2 = (int)(x2[i] - 1) / d + 1;
int cy2 = (int)(y2[i] - 1) / d + 1;
if(cx1 == cx2 && cy1 == cy2)
{
int tt = (x2[i] - x1[i] + 1) * (y2[i] - y1[i] + 1);
add(cx1, cy1, tt, s1, s2);
}
else if(cx1 == cx2 && cy1 != cy2)
{
/// colt stanga
int tt = ((d * cy1) - y1[i] + 1) * (x2[i] - x1[i] + 1);
add(cx1, cy1, tt, s1, s2);
/// colt dreapta
tt = (y2[i] - d * (cy2 - 1)) * (x2[i] - x1[i] + 1);
add(cx2, cy2, tt, s1, s2);
/// mijloc
if(cy2 - cy1 - 1 >= 1)
{
int tt = d * (x2[i] - x1[i] + 1);
int np = cy2 - cy1 - 1;
int nri = np / 2, nrp = np / 2;
if(np % 2 == 1)
nri++;
add(cx1, cy1 + 1, tt * nri, s1, s2);
add(cx1, cy1 + 2, tt * nrp, s1, s2);
}
}
else if(cx1 != cx2 && cy1 == cy2)
{
/// colt sus
int tt = ((d * cx1) - x1[i] + 1) * (y2[i] - y1[i] + 1);
add(cx1, cy1, tt, s1, s2);
/// colt jos
tt = (x2[i] - d * (cx2 - 1)) * (y2[i] - y1[i] + 1);
add(cx2, cy2, tt, s1, s2);
/// mijloc
if(cx2 - cx1 - 1 >= 1)
{
int tt = d * (y2[i] - y1[i] + 1);
int np = cx2 - cx1 - 1;
int nri = np / 2, nrp = np / 2;
if(np % 2 == 1)
nri++;
add(cx1 + 1, cy1, tt * nri, s1, s2);
add(cx1 + 2, cy1, tt * nrp, s1, s2);
}
}
else
{
/// colt st sus
int tt = (d * cx1 - x1[i] + 1) * (d * cy1 - y1[i] + 1);
add(cx1, cy1, tt, s1, s2);
/// colt dr sus
tt = (d * cx1 - x1[i] + 1) * (y2[i] - d * (cy2 - 1));
add(cx1, cy2, tt, s1, s2);
/// colt st jos
tt = (x2[i] - d * (cx2 - 1)) * (d * cy1 - y1[i] + 1);
add(cx2, cy1, tt, s1, s2);
/// colt dr jos
tt = (x2[i] - d * (cx2 - 1)) * (y2[i] - d * (cy2 - 1));
add(cx2, cy2, tt, s1, s2);
/// marg sus si jos
if(cy2 - cy1 - 1 >= 1)
{
tt = (d * cx1 - x1[i] + 1) * d;
int np = cy2 - cy1 - 1;
int nri = np / 2, nrp = np / 2;
if(np % 2 == 1)
nri++;
add(cx1, cy1 + 1, tt * nri, s1, s2);
add(cx1, cy1 + 2, tt * nrp, s1, s2);
tt = (x2[i] - d * (cx2 - 1)) * d;
add(cx2, cy1 + 1, tt * nri, s1, s2);
add(cx2, cy1 + 2, tt * nrp, s1, s2);
}
/// marg st si dr
if(cx2 - cx1 - 1 >= 1)
{
tt = (d * cy1 - y1[i] + 1) * d;
int np = cx2 - cx1 - 1;
int nri = np / 2, nrp = np / 2;
if(np % 2 == 1)
nri++;
add(cx1 + 1, cy1, tt * nri, s1, s2);
add(cx1 + 2, cy1, tt * nrp, s1, s2);
tt = (y2[i] - d * (cy2 - 1)) * d;
add(cx1 + 1, cy2, tt * nri, s1, s2);
add(cx1 + 2, cy2, tt * nrp, s1, s2);
}
/// mijloc
if((cx2 - cx1 - 1) * (cy2 - cy1 - 1) >= 1)
{
int nrp = (cx2 - cx1 - 1) * (cy2 - cy1 - 1);
int d1 = nrp / 2, d2 = nrp / 2;
if(nrp % 2 == 1)
d1++;
add(cx1 + 1, cx2 + 1, d * d1, s1, s2);
add(cx1 + 1, cx2 + 2, d * d2, s1, s2);
}
}
}
int d1 = (int)(n * n / d) / 2, d2 = (int)(n * n / d) / 2;
if((n * n / d) % 2 == 1)
d1++;
d1 = (int)(d1 * d), d2 = (int)(d2 * d);
int ans = min(d1 - s1 + s2, d2 - s2 + s1);
minn = min(minn, ans);
}
cout<<minn<<'\n';
return 0;
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:22:9: warning: unused variable 's1' [-Wunused-variable]
22 | int s1 = 0, s2 = 0;
| ^~
chessboard.cpp:22:17: warning: unused variable 's2' [-Wunused-variable]
22 | int s1 = 0, s2 = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
2248 KB |
Output is correct |
| 2 |
Correct |
19 ms |
876 KB |
Output is correct |
| 3 |
Correct |
44 ms |
1488 KB |
Output is correct |
| 4 |
Correct |
45 ms |
1632 KB |
Output is correct |
| 5 |
Correct |
60 ms |
1992 KB |
Output is correct |
| 6 |
Correct |
36 ms |
1328 KB |
Output is correct |
| 7 |
Correct |
8 ms |
468 KB |
Output is correct |
| 8 |
Correct |
57 ms |
1388 KB |
Output is correct |
| 9 |
Correct |
92 ms |
3084 KB |
Output is correct |
| 10 |
Correct |
52 ms |
1768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
2248 KB |
Output is correct |
| 2 |
Correct |
19 ms |
876 KB |
Output is correct |
| 3 |
Correct |
44 ms |
1488 KB |
Output is correct |
| 4 |
Correct |
45 ms |
1632 KB |
Output is correct |
| 5 |
Correct |
60 ms |
1992 KB |
Output is correct |
| 6 |
Correct |
36 ms |
1328 KB |
Output is correct |
| 7 |
Correct |
8 ms |
468 KB |
Output is correct |
| 8 |
Correct |
57 ms |
1388 KB |
Output is correct |
| 9 |
Correct |
92 ms |
3084 KB |
Output is correct |
| 10 |
Correct |
52 ms |
1768 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
