#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
using namespace std;
typedef long long ll;
const int N = 100002;
int n, k, f[N][2];
pair <int, int> a[N];
vector <vector <int> > v;
int mau(int x, int id){
int col = x%2;
if(col==0 && id==0) col = 1;
else if(col==1){
col = id;
}
return col;
}
int solve2(vector <pair <int, int> > cur, int sz, int id){
int Sz = cur.size();
int res = 0;
for(int i = 0; i < Sz - 1; i++){
auto t = cur[i + 1];
auto t2 = cur[i];
int x = cur[i + 1].first - cur[i].first;
if(x==1){
if(i==Sz - 2) break;
if(cur[i + 1].first > (n/sz)) continue;
int col = mau(cur[i + 1].first, id);
if(col==1) res = res + sz*sz - cur[i + 1].second;
else res = res + cur[i + 1].second;
}
else{
int k1 = mau(cur[i].first + 1, id);
int k2 = mau(cur[i + 1].first - 1, id);
int y = cur[i + 1].first - cur[i].first - 1;
if(k1 + k2 <= 1){
y /= 2;
res = res + (sz*sz)*y;
}
else{
y = (y + 1)/2;
res = res + (sz*sz)*y;
}
if(i + 1==int(cur.size() - 1)) break;
int col = mau(cur[i + 1].first, id);
if(col==1) res = res + sz*sz - cur[i + 1].second;
else res = res + cur[i + 1].second;
}
}
return res;
}
int solve(int s){
f1(i, s) v[i].clear();
f1(i, k){
int k1 = (a[i].first - 1)/s + 1;
int k2 = (a[i].second - 1)/s + 1;
v[k1].emplace_back(k2);
}
vector <pair <int, int> > now;
f1(i, (n/s)){
now.clear();
now.emplace_back(0, s*s);
for(int j = 0; j < v[i].size(); j++){
int cur = j;
int e = v[i][j];
for(cur = j; cur < v[i].size(); cur++){
if(v[i][cur] != v[i][j]) break;
}
now.emplace_back(v[i][j], cur - j);
j = cur - 1;
int u = v[i][j];
int g = v[i][j];
}
now.emplace_back((n/s) + 1, s*s);
f[i][0] = f[i][1] = 1e9;
f[i][0] = solve2(now, s, 0);
f[i][1] = solve2(now, s, 1);
}
int x1 = 0, x2 = 0;
f1(i, (n/s)){
if(i%2) x1 = x1 + f[i][1], x2 = x2 + f[i][0];
else x1 = x1 + f[i][0], x2 = x2 + f[i][1];
}
return min(x1, x2);
}
int main(){
ios_base::sync_with_stdio(0);
cin >> n >> k;
v.resize(n + 1);
f1(i, k){
int x, y, u, v; cin >> x >> y >> u >> v;
a[i] = {x, y};
}
sort(a + 1, a + k + 1);
int res = 21e8;
f1(i, sqrt(n)){
int j = n/i;
if(i*j==n){
if(i != n)
res = min(res, solve(i));
if(j != n)
res = min(res, solve(j));
}
}
cout << res;
}
Compilation message
chessboard.cpp: In function 'int solve2(std::vector<std::pair<int, int> >, int, int)':
chessboard.cpp:26:14: warning: variable 't' set but not used [-Wunused-but-set-variable]
auto t = cur[i + 1];
^
chessboard.cpp:27:14: warning: variable 't2' set but not used [-Wunused-but-set-variable]
auto t2 = cur[i];
^~
chessboard.cpp: In function 'int solve(int)':
chessboard.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < v[i].size(); j++){
~~^~~~~~~~~~~~~
chessboard.cpp:71:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(cur = j; cur < v[i].size(); cur++){
~~~~^~~~~~~~~~~~~
chessboard.cpp:70:17: warning: unused variable 'e' [-Wunused-variable]
int e = v[i][j];
^
chessboard.cpp:76:17: warning: unused variable 'u' [-Wunused-variable]
int u = v[i][j];
^
chessboard.cpp:77:17: warning: unused variable 'g' [-Wunused-variable]
int g = v[i][j];
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
520 KB |
Output is correct |
6 |
Correct |
2 ms |
524 KB |
Output is correct |
7 |
Correct |
2 ms |
576 KB |
Output is correct |
8 |
Correct |
2 ms |
580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
5844 KB |
Output is correct |
2 |
Correct |
15 ms |
5844 KB |
Output is correct |
3 |
Incorrect |
40 ms |
7424 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
5844 KB |
Output is correct |
2 |
Correct |
15 ms |
5844 KB |
Output is correct |
3 |
Incorrect |
40 ms |
7424 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
520 KB |
Output is correct |
6 |
Correct |
2 ms |
524 KB |
Output is correct |
7 |
Correct |
2 ms |
576 KB |
Output is correct |
8 |
Correct |
2 ms |
580 KB |
Output is correct |
9 |
Correct |
51 ms |
5844 KB |
Output is correct |
10 |
Correct |
15 ms |
5844 KB |
Output is correct |
11 |
Incorrect |
40 ms |
7424 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |