Submission #313142

#	Time	Username	Problem	Language	Result	Execution time	Memory
313142		tengiz05	Wiring (IOI17_wiring)	C++17	0 / 100	48 ms	4088 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 = (s+1)/2;
		long long mn1 = min(mn, f);
		ans += mn1*mn1;
		f -= mn1;mn -= mn1;
		for(;f>0;f--)ans += mn1+f;
		for(;mn>0;mn--)ans += mn1+mn;
		v[i] = s/2;
	}for(;v[n-1]>0;v[n-1]--)ans += last-v[n-1]+1ll;
	return ans;
}
/*

5 4
1 5 6 8 9
2 3 4 7

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

*/

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