Submission #332555

#	Time	Username	Problem	Language	Result	Execution time	Memory
332555		MetB	Wiring (IOI17_wiring)	C++14	0 / 100	72 ms	15316 KiB

wiring

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const int N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

ll d[N];

void process(vector<ll>& fst, vector<ll>& snd, ll from) {
	if(fst.empty()) return;

	vector<ll> dleft(snd.size() + 1, INF), dright(snd.size() + 1, INF);

	from -= (ll)fst.size() + (ll)snd.size();
	
	ll dist = snd[0] - fst.back();
	ll sum_len = 0, sz = 0;

	for (ll i = fst.size(); i >= 0; i--) {
		ll last = (i + from ? d[i + from - 1] : 0);

		if (i != fst.size()) sum_len += fst.back() - fst[i];

		dleft[sz] = last + sum_len;
		dright[sz] = last + sum_len + sz * dist;
		sz++;
	}

	for (ll i = 1; i <= snd.size(); i++) {
		dleft[i] = min(dleft[i-1], dleft[i]);
	}

	for (ll i = snd.size() - 1; i >= 0; i--) {
		dright[i] = min(dright[i+1], dright[i]);
	}

	sum_len = 0;

	from += (ll)fst.size();
	for (ll i = 0; i < snd.size(); i++) {
		sum_len += snd[i] - snd[0];
		d[i + from] = sum_len;
		d[i + from] += min(dright[i+1], dleft[i+1] + (i + 1) * dist);
	}
}

ll min_total_length(vector<int> r, vector<int> b) {
	auto pr = r.begin(), pb = b.begin();

	ll n = r.size() + b.size();

	fill(d, d + n, INF);

	struct poll {
		ll x;
		char color;

		bool operator<(poll b) {
			return x < b.x;
		}
	};

	vector<poll> v;
	vector<ll> red, blue;

	for (ll a : r) {
		v.push_back({a, 'r'});
	}

	for (ll a : b) {
		v.push_back({a, 'b'});
	}

	sort(v.begin(), v.end());

	for (ll i = 0; i < n; i++) {
		if (i && v[i-1].color != v[i].color) {
			if (v[i].color == 'r') {
				process(red, blue, i);
				red.clear();
			}
			else {
				process(blue, red, i);
				blue.clear();
			}
		}

		if (v[i].color == 'r') red.push_back(v[i].x);
		else blue.push_back(v[i].x);
	}

	if(v.back().color == 'r') process(blue, red, n);
	else process(red, blue, n);

	return d[v.size() - 1];
}

/*ll main () {
	ll sr, sb;
	cin >> sr >> sb;

	vector<ll> r, b;

	for (ll i = 0; i < sr; i++) {
		ll x;
		cin >> x;
		r.push_back(x);
	}

	for (ll i = 0; i < sb; i++) {
		ll x;
		cin >> x;
		b.push_back(x);
	}

	cout << min_total_length(r, b);
}*/

Compilation message (stderr)

wiring.cpp: In function 'void process(std::vector<long long int>&, std::vector<long long int>&, ll)':
wiring.cpp:31:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   if (i != fst.size()) sum_len += fst.back() - fst[i];
      |       ~~^~~~~~~~~~~~~
wiring.cpp:38:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (ll i = 1; i <= snd.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
wiring.cpp:49:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (ll i = 0; i < snd.size(); i++) {
      |                 ~~^~~~~~~~~~~~
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:57:7: warning: variable 'pr' set but not used [-Wunused-but-set-variable]
   57 |  auto pr = r.begin(), pb = b.begin();
      |       ^~
wiring.cpp:57:23: warning: variable 'pb' set but not used [-Wunused-but-set-variable]
   57 |  auto pr = r.begin(), pb = b.begin();
      |                       ^~

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