Submission #284321

#	Time	Username	Problem	Language	Result	Execution time	Memory
284321		Berted	Wiring (IOI17_wiring)	C++14	13 / 100	38 ms	4608 KiB

wiring

#include "wiring.h"
#include <vector>
#include <stack>
#include <algorithm>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int INF = 1e9 + 7;

stack<pii> S;
ll ret = 0;


ll min_total_length(vector<int> r, vector<int> b) 
{
	int i = 0, j = 0;
	while (i < r.size() || j < b.size())
	{
		int valL = (i < r.size()) ? r[i] : INF;
		int valR = (j < b.size()) ? b[j] : INF;
		if (valL < valR)
		{
			if (S.size() && S.top().snd) {ret += valL - S.top().fst; S.pop();}
			else {S.push({valL, 0});}
			i++;
		} 
		else
		{
			if (S.size() && !S.top().snd) {ret += valR - S.top().fst; S.pop();}
			else {S.push({valR, 1});} 
			j++;
		}
	} 
	while (S.size())
	{
		int add = INF;
		if (S.top().snd)
		{
			auto it = upper_bound(r.begin(), r.end(), S.top().fst);
			if (it != r.end()) {add = min(add, *it - S.top().fst);}
			if (it != r.begin()) {add = min(add, S.top().fst - *prev(it));}
		}
		else
		{
			auto it = upper_bound(b.begin(), b.end(), S.top().fst);
			if (it != b.end()) {add = min(add, *it - S.top().fst);}
			if (it != b.begin()) {add = min(add, S.top().fst - *prev(it));}
		}
		S.pop(); ret += add;
	}
	return ret;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  while (i < r.size() || j < b.size())
      |         ~~^~~~~~~~~~
wiring.cpp:21:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  while (i < r.size() || j < b.size())
      |                         ~~^~~~~~~~~~
wiring.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   int valL = (i < r.size()) ? r[i] : INF;
      |               ~~^~~~~~~~~~
wiring.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   int valR = (j < b.size()) ? b[j] : INF;
      |               ~~^~~~~~~~~~

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