Submission #208482

#	Time	Username	Problem	Language	Result	Execution time	Memory
208482		Siberian	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	6 ms	376 KiB

joi2019_ho_t4

#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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63