Submission #420965

#	Time	Username	Problem	Language	Result	Execution time	Memory
420965		albertolg101	Wiring (IOI17_wiring)	C++17	13 / 100	154 ms	16944 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

using namespace std;

using ll = long long;
using pii = pair<ll, int>;

const int INF = 2e9;

void print (vector<pii> v)
{
	for(auto i: v)
		cout << i.first << ' ' << i.second << endl ; 
	cout << endl ;
}

void print (vector<ll> v)
{
	for(auto i: v)
		cout << i << ' ' ; 
	cout << endl ;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {

	vector<pii> ar;

	for(auto i: r)
		ar.push_back({i, 0});

	for(auto i: b)
		ar.push_back({i, 1});

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

	ar.insert(ar.begin(), (pii){0, 0});

	int acc = 0;
	map<int, int> mfirst, mlast;
	vector<long long> cost;


	mfirst[0] = 0;
	mlast[0] = 0;
	cost.push_back(0);

	for(int i = 1 ; i < ar.size() ; i++)
	{
		ar[i].second ? acc++ : acc--;

		if(mlast.count(acc))
		{
			if(mlast[acc] + 2 == i)
				cost.push_back(cost[mlast[acc]] + ar[i].first - ar[i-1].first);

			else
				cost.push_back(cost[mlast[acc]] + cost[i-1] - cost[mlast[acc] + 1] + ar[i].first - ar[mlast[acc] + 1].first);

			mlast[acc] = i;
		}

		else
		{
			long long temp = INF;

			if(ar[i].second == 0) //b
				swap(b, r);

			auto pt = lower_bound(r.begin(), r.end(), ar[i].first);
			if(pt != r.end())
				temp = *pt - ar[i].first ;
			if(pt != r.begin())
				temp = min(temp, ar[i].first - *prev(pt));

			if(ar[i].second == 0)
				swap(b, r);

			cost.push_back(cost[i-1] + temp);
			mlast[acc] = mfirst[acc] = i ;
		}
	}

	//print(ar);
	//print(cost);

	return cost.back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 1 ; i < ar.size() ; i++)
      |                  ~~^~~~~~~~~~~

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