oj.uz

Submission #998912

# Submission time Handle Problem Language Result Execution time Memory
998912 2024-06-14T23:04:12 Z izanbf Wiring (IOI17_wiring) C++14
0 / 100
 0 ms 348 KB 
#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;

int closest(int x, vi& v) {
	int ans = 2e9;
	for (int y : v) {
		ans = min(ans, abs(x - y));
	}
	return ans;
}

ll min_total_length(vi r, vi b) {
	sort(r.begin(), r.end());
	sort(b.begin(), b.end());

	queue<int> red, blue;

	int i = 0, j = 0;
	int n = r.size(), m = b.size();
	ll ans = 0;

	cout << n << ' ' << m << endl;

	while (i < n and j < m) {
		if (r[i] < b[j]) { // r
			if (blue.empty()) {
				red.push(i);
				// cerr << "PUSH red " << i << endl;
			}
			else {
				ans += abs(r[i] - b[blue.front()]);
				// cerr << "a$ " << r[i] << ' ' << b[blue.front()] << ' ' << blue.front() << endl;
				blue.pop();
			}
			++i;
		}
		else { // b
			if (red.empty()) {
				blue.push(j);
				// cerr << "PUSH blue " << j << endl;
			}
			else {
				ans += abs(b[j] - r[red.front()]);
				// cerr << "b$ " << r[red.front()] << ' ' << b[j] << ' ' << red.front() << endl;
				red.pop();
			}
			++j;
		}
	}

	while (i < n) {
		if (blue.empty()) {
			red.push(i);
		}
		else {
			ans += abs(r[i] - b[blue.front()]);
			// cerr << "x$ " << r[i] << ' ' << b[blue.front()] << endl;
			blue.pop();
		}
		++i;
	}

	while (j < m) {
		if (red.empty()) {
			blue.push(j);
		}
		else {
			ans += abs(b[j] - r[red.front()]);
			// cerr << "x$ " << r[red.front()] << ' ' << b[j] << endl;
			red.pop();
		}
		++j;
	}

	// cout << red.size() << ' ' << blue.size() << endl;

	while (not red.empty()) {
		int x = r[red.front()];
		red.pop();
		ans += closest(x, b);
	}

	while (not blue.empty()) {
		int x = b[blue.front()];
		blue.pop();
		ans += closest(x, r);
	}

	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -