Submission #39057792

---

Source Code Expand

#pragma GCC optimize(3)
#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf64 = 0x3f3f3f3f3f3f3f3f;

constexpr int N = 305;
constexpr int M = 305;

constexpr double dt = 0.9997;

int n, m;
int a[N], b[M];
int p[N + M];

i64 ans;
int s[N + M];

int t1[N], t2[M];

i64 calc () {
	int k1 = 0, k2 = 0;
	std::memset(s + 1, 0, n + m << 2);
	for (int i = 1; i <= n; ++ i) {
		s[p[i]] = 1;
	}
	for (int i = 1; i <= n + m; ++ i) {
		if (s[i] == 0) {
			t2[++ k2] = std::abs(n - 2 * s[i - 1]);
		} else {
			t1[++ k1] = std::abs(m - 2 * ((i - 1) - s[i - 1]));
		}
		s[i] += s[i - 1];
	}
	
//	std::sort(c1 + 1, c1 + n + 1);
//	std::sort(c2 + 1, c2 + m + 1);
	
	i64 res = 0LL;
	
	for (int i = 1, j = n, p = 1; i <= j; ) {
		if (t1[i] >= t1[j]) {
			res += 1LL * a[p ++ ] * t1[i ++ ];
		} else {
			res += 1LL * a[p ++ ] * t1[j -- ];
		}
	}
	
	for (int i = 1, j = m, p = 1; i <= j; ) {
		if (t2[i] >= t2[j]) {
			res += 1LL * b[p ++ ] * t2[i ++ ];
		} else {
			res += 1LL * b[p ++ ] * t2[j -- ];
		}
	}
	
	ans = std::min(ans, res);
	return res;
}

int main () {
	
	auto Bg = clock();
	auto Time = [&]() -> double {
		return double(clock() - Bg) / CLOCKS_PER_SEC;
	};
	
	std::ios::sync_with_stdio(0);
	std::cin.tie(nullptr);
	
	srand(time(0) * ((unsigned long long)new char));
	
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i) {
		std::cin >> a[i];
	}
	for (int i = 1; i <= m; ++ i) {
		std::cin >> b[i];
	}
	
	std::sort(a + 1, a + n + 1);
	std::sort(b + 1, b + m + 1);
	
	std::iota(p + 1, p + (n + m) + 1, 1);
	std::shuffle(p + 1, p + (n + m) + 1, std::mt19937 (1206));
	
	ans = inf64;
	i64 cur = calc();
	
	for (double t = 1e6; Time() < 1.9; t *= dt) {
		int i = rand() % n + 1, j = rand() % m + n + 1;
		std::swap(p[i], p[j]);
		i64 nxt = calc();
		if (nxt <= cur) {
			cur = nxt;
		} else {
			const double prob = exp(-(nxt - cur) / t);
			if (rand() < prob * 2147483647) {
				cur = nxt;
			} else {
				std::swap(p[i], p[j]);
			}
		}
	}
	
	std::cout << ans << "\n";
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘i64 calc()’:
./Main.cpp:24:26: warning: suggest parentheses around ‘+’ inside ‘<<’ [-Wparentheses]
   24 |  std::memset(s + 1, 0, n + m << 2);
      |                        ~~^~~

Judge Result