//#ifndef LOCAL
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif
#include <bits/stdc++.h>
using namespace std;
using vecp = vector<pair<int,int>>;
#define vecm(a,n,m) vector<vector<int>>a(n,vector<int>(m,0));
#define int int64_t
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mpii map<int,int>
#define lb lower_bound
#define ub upper_bound
#define foor(i,a,b) for(int i=a;i<b; i++)
#define foor(i,a) foor(i,0,a)
#define ins insert
#define ss second
#define ff first
#define until(x, a) for (auto x : a)
#define ln(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define seea(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
const int mod = 1E9+7;
bool tub(int n){
for(int i=2; i*i<=n; i++){
if(n%i==0)return false;
}
return true;
}
void solution(){
int n,k;
cin >> n >> k;
if(tub(n) && k>0){
int f=n/2*(n/2+1)*2;
int s=(n/2+1)*(n/2+1)+(n/2)*(n/2);
while(k--){
int a,b,c,d;
cin >> a >> b >> c >> d;
a--;b--;
if(a%2==b%2){
s--;f++;
}
else {
s++;f--;
}
}
cout << min(s,f);
}
else {
//vector<vector<int>> vec(n,vector<int>(n,0));
vector<pair<int,int>> p;
vector<int> mx;
while(k--){
int a,b,c,d;
cin >> a >> b >> c >> d;
a--;b--;c--;d--;
p.pb({a,b});
}
for(int i=1; i<=n/2; i++){
if(n%i==0){
int x=n/i;
int f=1e18,s=1e18;
if(x%2==0){
f=s=(i*i)*x/2*n/i;
}
else {
s=x/2*(x/2+1)*2*(i*i);
f=(i*i)*((x/2+1)*(x/2+1)+(x/2)*(x/2));
}
// for(int k=0; k<n; k++){
// for(int j=0; j<n; j++){
// int fg=k/i+1;
// int sg=j/i+1;
// if(vec[k][j]==1){
// cnt++;
// if(fg%2==sg%2){
// s++;f--;
// }
// else {
// f++;s--;
// }
// }
// }
// }
for(int k=0; k<p.size(); k++){
int fg=p[k].ff/i+1;
int sg=p[k].ss/i+1;
if(fg%2==sg%2){
s++;f--;
}
else {
f++;s--;
}
}
mx.push_back(f);
mx.push_back(s);
}
}
sort(all(mx));
cout << mx[0];
}
}
int32_t main(){
clock_t tStart = clock();
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while(q--) {
solution();
cout << '\n';
}
cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}
/*
██╗ ██╗ █████╗ ██████╗ ██╗██╗ ██╗ ██████╗████████╗
██║░░██║██╔══██╗██╔════╝░░░░░██║██║░░░██║██╔════╝╚══██╔══╝
███████║██║░░██║╚█████╗░░░░░░██║██║░░░██║╚█████╗░░░░██║░░░
██╔══██║██║░░██║░╚═══██╗██╗░░██║██║░░░██║░╚═══██╗░░░██║░░░
██║░░██║╚█████╔╝██████╔╝╚█████╔╝╚██████╔╝██████╔╝░░░██║░░░
╚═╝░░╚═╝░╚════╝░╚═════╝░░╚════╝░░╚═════╝░╚═════╝░░░░╚═╝░░░
*/
Compilation message
chessboard.cpp:19: warning: "foor" redefined
19 | #define foor(i,a) foor(i,0,a)
|
chessboard.cpp:18: note: this is the location of the previous definition
18 | #define foor(i,a,b) for(int i=a;i<b; i++)
|
chessboard.cpp: In function 'void solution()':
chessboard.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int k=0; k<p.size(); k++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
452 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
1720 KB |
Output is correct |
2 |
Correct |
4 ms |
604 KB |
Output is correct |
3 |
Correct |
9 ms |
1372 KB |
Output is correct |
4 |
Correct |
10 ms |
1116 KB |
Output is correct |
5 |
Correct |
13 ms |
1628 KB |
Output is correct |
6 |
Correct |
8 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
620 KB |
Output is correct |
8 |
Correct |
8 ms |
1116 KB |
Output is correct |
9 |
Correct |
22 ms |
2396 KB |
Output is correct |
10 |
Correct |
12 ms |
1628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
464 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
464 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
464 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
464 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
7 ms |
1500 KB |
Output is correct |
17 |
Correct |
16 ms |
1624 KB |
Output is correct |
18 |
Correct |
31 ms |
3796 KB |
Output is correct |
19 |
Correct |
50 ms |
3796 KB |
Output is correct |
20 |
Correct |
56 ms |
3800 KB |
Output is correct |
21 |
Correct |
16 ms |
1712 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
14 ms |
2268 KB |
Output is correct |
24 |
Correct |
22 ms |
3800 KB |
Output is correct |
25 |
Correct |
3 ms |
860 KB |
Output is correct |
26 |
Correct |
14 ms |
2264 KB |
Output is correct |
27 |
Correct |
19 ms |
3536 KB |
Output is correct |
28 |
Correct |
23 ms |
3800 KB |
Output is correct |
29 |
Correct |
7 ms |
860 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
1720 KB |
Output is correct |
2 |
Correct |
4 ms |
604 KB |
Output is correct |
3 |
Correct |
9 ms |
1372 KB |
Output is correct |
4 |
Correct |
10 ms |
1116 KB |
Output is correct |
5 |
Correct |
13 ms |
1628 KB |
Output is correct |
6 |
Correct |
8 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
620 KB |
Output is correct |
8 |
Correct |
8 ms |
1116 KB |
Output is correct |
9 |
Correct |
22 ms |
2396 KB |
Output is correct |
10 |
Correct |
12 ms |
1628 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
464 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
464 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
7 ms |
1500 KB |
Output is correct |
27 |
Correct |
16 ms |
1624 KB |
Output is correct |
28 |
Correct |
31 ms |
3796 KB |
Output is correct |
29 |
Correct |
50 ms |
3796 KB |
Output is correct |
30 |
Correct |
56 ms |
3800 KB |
Output is correct |
31 |
Correct |
16 ms |
1712 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
14 ms |
2268 KB |
Output is correct |
34 |
Correct |
22 ms |
3800 KB |
Output is correct |
35 |
Correct |
3 ms |
860 KB |
Output is correct |
36 |
Correct |
14 ms |
2264 KB |
Output is correct |
37 |
Correct |
19 ms |
3536 KB |
Output is correct |
38 |
Correct |
23 ms |
3800 KB |
Output is correct |
39 |
Correct |
7 ms |
860 KB |
Output is correct |
40 |
Correct |
1 ms |
468 KB |
Output is correct |
41 |
Correct |
48 ms |
4204 KB |
Output is correct |
42 |
Correct |
30 ms |
4416 KB |
Output is correct |
43 |
Correct |
36 ms |
4408 KB |
Output is correct |
44 |
Correct |
26 ms |
4312 KB |
Output is correct |
45 |
Correct |
28 ms |
2744 KB |
Output is correct |
46 |
Correct |
53 ms |
4304 KB |
Output is correct |
47 |
Correct |
20 ms |
2384 KB |
Output is correct |
48 |
Correct |
30 ms |
4312 KB |
Output is correct |
49 |
Correct |
24 ms |
4312 KB |
Output is correct |
50 |
Correct |
186 ms |
4312 KB |
Output is correct |
51 |
Correct |
201 ms |
4304 KB |
Output is correct |
52 |
Correct |
184 ms |
4276 KB |
Output is correct |
53 |
Correct |
196 ms |
4308 KB |
Output is correct |
54 |
Correct |
182 ms |
4208 KB |
Output is correct |
55 |
Correct |
206 ms |
4356 KB |
Output is correct |
56 |
Correct |
180 ms |
4284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
452 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
15 ms |
1720 KB |
Output is correct |
10 |
Correct |
4 ms |
604 KB |
Output is correct |
11 |
Correct |
9 ms |
1372 KB |
Output is correct |
12 |
Correct |
10 ms |
1116 KB |
Output is correct |
13 |
Correct |
13 ms |
1628 KB |
Output is correct |
14 |
Correct |
8 ms |
1116 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
8 ms |
1116 KB |
Output is correct |
17 |
Correct |
22 ms |
2396 KB |
Output is correct |
18 |
Correct |
12 ms |
1628 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
464 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
464 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
7 ms |
1500 KB |
Output is correct |
35 |
Correct |
16 ms |
1624 KB |
Output is correct |
36 |
Correct |
31 ms |
3796 KB |
Output is correct |
37 |
Correct |
50 ms |
3796 KB |
Output is correct |
38 |
Correct |
56 ms |
3800 KB |
Output is correct |
39 |
Correct |
16 ms |
1712 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
14 ms |
2268 KB |
Output is correct |
42 |
Correct |
22 ms |
3800 KB |
Output is correct |
43 |
Correct |
3 ms |
860 KB |
Output is correct |
44 |
Correct |
14 ms |
2264 KB |
Output is correct |
45 |
Correct |
19 ms |
3536 KB |
Output is correct |
46 |
Correct |
23 ms |
3800 KB |
Output is correct |
47 |
Correct |
7 ms |
860 KB |
Output is correct |
48 |
Correct |
1 ms |
468 KB |
Output is correct |
49 |
Correct |
48 ms |
4204 KB |
Output is correct |
50 |
Correct |
30 ms |
4416 KB |
Output is correct |
51 |
Correct |
36 ms |
4408 KB |
Output is correct |
52 |
Correct |
26 ms |
4312 KB |
Output is correct |
53 |
Correct |
28 ms |
2744 KB |
Output is correct |
54 |
Correct |
53 ms |
4304 KB |
Output is correct |
55 |
Correct |
20 ms |
2384 KB |
Output is correct |
56 |
Correct |
30 ms |
4312 KB |
Output is correct |
57 |
Correct |
24 ms |
4312 KB |
Output is correct |
58 |
Correct |
186 ms |
4312 KB |
Output is correct |
59 |
Correct |
201 ms |
4304 KB |
Output is correct |
60 |
Correct |
184 ms |
4276 KB |
Output is correct |
61 |
Correct |
196 ms |
4308 KB |
Output is correct |
62 |
Correct |
182 ms |
4208 KB |
Output is correct |
63 |
Correct |
206 ms |
4356 KB |
Output is correct |
64 |
Correct |
180 ms |
4284 KB |
Output is correct |
65 |
Correct |
0 ms |
348 KB |
Output is correct |
66 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
67 |
Halted |
0 ms |
0 KB |
- |