#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ff first
#define ss second
#pragma GCC optimize("Ofast","inline","-ffast-math")
signed main(){
int n, m, mn = 1e18; cin >> n >> m;
int rev = n * n;
vector<vector<int>> v(n, vector<int>(n, 0));
while(m--){
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
x1--; y1--; x2--; y2--;
for(int i = x1; i <= x2; i++){
for(int j = y1; j <= y2; j++) v[i][j] = 1;
}
} int cnt1 = 0, cnt2 = 0;
vector<vector<int>> res1(n, vector<int>(n, 0));
vector<vector<int>> res2;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(n % 2 == 0){
if((j + (i * (n - 1))) % 2 == 0) res1[i][j] = 0;
else res1[i][j] = 1;
} else {
if((j + (i * n)) % 2 == 0) res1[i][j] = 0;
else res1[i][j] = 1;
}
}
} for(int i = 0; i < n; i++){
vector<int> answer_;
for(int j = 0; j < n; j++){
answer_.emplace_back(res1[i][j]);
} res2.emplace_back(answer_);
} reverse(res2.begin(), res2.end());
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(res1[i][j] != v[i][j]) cnt1++;
//cout << res1[i][j] << " ";
}
//cout << "\n";
} //cout << "\n";
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(res2[i][j] != v[i][j]) cnt2++;
//cout << res2[i][j] << " ";
}
//cout << "\n";
} //cout << "\n";
mn = min(mn, cnt1);
mn = min(mn, cnt2);
//cout << cnt1 << " " << cnt2 << "\n";
vector<vector<int>> qwer;
//cout << cnt1 << " " << cnt2 << "\n";
for(int k = 2; k <= n - 1; k++){
vector<vector<int>> res(n, vector<int>(n, 0));
int cnt = 0;
if(n % k == 0){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i % k == 0 && j % k == 0){
cnt++;
if(cnt % 2 == 0){
for(int q = i; q < i + k; q++){
for(int w = j; w < j + k; w++){
res[q][w] = 1;
}
}
}
}
}
} int cur = 0;
vector<vector<int>> ans(n, vector<int>(n, 0));
for(int i = k; i < n; i++){
if((i + 1) % k == 0){
cur++;
if(cur % 2 != 0){
for(int q = i - (k - 1); q <= i; q++){
for(int j = 0; j < n; j++){
ans[q][j] = res[q][j];
res[q][j] = 0;
}
}
}
}
} vector<vector<int>> curr;
for(int i = 0; i < n; i++){
vector<int> result;
for(int j = n - 1; j >= 0; j--){
result.emplace_back(ans[i][j]);
} curr.emplace_back(result);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(res[i][j] == 1){
curr[i][j] = 1;
}
} //cout << "\n";
} //cout << "\n";
// if((n * n) % k == 0 && k == wer - 3){
// for(int i = 0; i < n; i++){
// vector<int> ert;
// for(int j = 0; j < n; j++){
// ert.emplace_back(curr[i][j]);
// } qwer.emplace_back(ert);
// }
// }
vector<vector<int>> cur_;
for(int i = 0; i < n; i++){
vector<int> rty;
for(int j = 0; j < n; j++){
rty.emplace_back(curr[i][j]);
} cur_.emplace_back(rty);
}
int count1 = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(v[i][j] != curr[i][j]){
count1++;
}
}
}
reverse(curr.begin(), curr.end());
int sovpadenie_A = 0;
// for(int i = 0; i < n; i++){
// for(int j = 0; j < n; j++){
// cout << cur_[i][j] << " ";
// } cout << "\n";
// } cout << "\n";
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(cur_[i][j] == curr[i][j]){
sovpadenie_A++;
}
//cout << curr[i][j] << " ";
} //cout << "\n";
} //cout << "\n";
if(sovpadenie_A == rev){
for(int i = 0; i < n; i++){
vector<int> pkl;
for(int j = 0; j < n; j++){
pkl.emplace_back(curr[i][j]);
} qwer.emplace_back(pkl);
}
} else {
int count2 = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(v[i][j] != curr[i][j]){
count2++;
}
}
} mn = min(count1, mn);
mn = min(mn, count2);
}
}
} //cout << mn << "\n";
if(n % 3 == 0){
vector<vector<int>> asd(n, vector<int> (n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(qwer[i][j] == 1){
asd[i][j] = 0;
} else if(qwer[i][j] == 0){
asd[i][j] = 1;
}
}
} int count__ = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(v[i][j] != asd[i][j]) count__++;
}
} mn = min(mn, count__);
}
cout << mn;
}
const int fastIO = [](){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
return 0;
}();
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
