Submission #312929

#	Time	Username	Problem	Language	Result	Execution time	Memory
312929		tengiz05	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	256 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
	vector<pair<int, bool>> a;
	for(auto x : r)a.push_back({x, 0});
	for(auto x : b)a.push_back({x, 1});
	sort(a.begin(), a.end());
	vector<long long> v;
	for(int i=0;i<(int)a.size(); i++){
		int cnt = 1;
		while(i+1 < (int)a.size() && a[i+1].second == a[i].second)cnt++,i++;
		v.push_back(cnt);
	}
	int n = v.size();
	long long ans = 0;
	long long f, s;
	long long last=0;
	for(int i=1;i<n;i++){
		f = v[i-1], s = v[i];
		last = s;
		if(f==0)continue;
		long long mn = min(f, s);
		ans += mn*mn;
		f -= mn;s -= mn;
		if(f > 0)for(;f>0;f--)ans += f+mn;
		v[i] = s;
	}if(v[n-1] > 0)for(;v[n-1]<last;v[n-1]++)ans += last-v[n-1]+1ll;
	return ans;
}
/*

5 4
1 5 6 8 9
2 3 4 7

8 3
1 2 3 5 8 9 10 11
4 6 7

*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45