#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()
template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
#define int ll
vector<int> x;
vector<int> y;
int n;
void read() {
cin >> n;
x.resize(2 * n);
y.resize(2 * n);
for (int i = 0; i < 2 * n; i++) {
cin >> x[i] >> y[i];
}
}
ll get(int l, int r, const vector<int> & a) {
int n = a.size();
vector<int> cnt(r - l + 1);
ll ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] < l) {
ans += l - a[i];
cnt[0]++;
}
else if (a[i] > r) {
ans += a[i] - r;
cnt[r - l]++;
}
else {
cnt[a[i] - l]++;
}
}
/*cout << "ans = " << ans << endl;
for (auto i : cnt)
cout << i << " ";
cout << endl;*/
for (int i = 1; i <= r - l; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = 0; i < r - l; i++) {
ans += abs((i + 1) * (n / (r - l + 1)) - cnt[i]);
//cout << (i + 1) * (n / (r - l + 1)) << " " << cnt[i] << endl;
}
//cout << "ans = " << ans << endl;
return ans;
}
ll ans;
int get(vector<int> & a, int len) {
int l = -1e9 - 10, r = 1e9 + 10;
while (l < r - 3) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
//cout << mid1 << " " << mid2 << endl;
if (get(mid1, mid1 + len - 1, a) > get(mid2, mid2 + len - 1, a))
l = mid1;
else
r = mid2;
}
int ans = l;
ll fans = get(l, l + len - 1, a);
for (int i = l + 1; i <= r; i++) {
ll have = get(i, i + len - 1, a);
if (have < fans) {
fans = have;
ans = i;
}
}
return ans;
}
void run() {
sort(all(x));
/*cout << "x = " << endl;
for (auto i : x)
cout << i << " ";
cout << endl;*/
sort(all(y));
/*cout << "y = " << endl;
for (auto i : y)
cout << i << " ";
cout << endl;*/
int fx = get(x, n);
int fy = get(y, 2);
//int fx = 1, fy = 1;
//cout << "fx = " << fx << endl;
//cout << "fy = " << fy << endl;
//get(fx, fx + n - 1, x);
//exit(0);
//cout << "get_x = " << get(fx, fx + n - 1, x) << endl;
//cout << "get_y = " << get(fy, fy + 1, y) << endl;
ans = get(fx, fx + n - 1, x) + get(fy, fy + 1, y);
}
void write() {
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
read();
run();
write();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
