Submission #284372

#	Time	Username	Problem	Language	Result	Execution time	Memory
284372		Berted	Wiring (IOI17_wiring)	C++14	100 / 100	52 ms	11292 KiB

wiring

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

using namespace std;

const ll INF = 1e9 + 7, INF2 = 1e18 + 7;

vector<pii> A;
int C[200001];
ll dp[200001], pref[200001], nx[200001];

void get(bool t)
{
	stack<int> s;
	for (int i = 0; i < A.size(); i++)
	{
		if (A[i].snd == t) {s.push(i);}
		else if (s.size()) {nx[i + 1] = s.top(); s.pop();}
	}
}

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) 
		{
			A.push_back({valL, 0}); 
			C[A.size() - 1] = INF;
			if (j < b.size()) {C[A.size() - 1] = min(C[A.size() - 1], b[j] - valL);}
			if (j) {C[A.size() - 1] = min(C[A.size() - 1], valL - b[j - 1]);}
			i++;
		} 
		else 
		{
			A.push_back({valR, 1}); 
			C[A.size() - 1] = INF;
			if (i < r.size()) {C[A.size() - 1] = min(C[A.size() - 1], r[i] - valR);}
			if (i) {C[A.size() - 1] = min(C[A.size() - 1], valR - r[i - 1]);}
			j++;
		}
	} 
	for (i = 1; i <= A.size(); i++) 
	{
		nx[i] = -1;
		if (A[i - 1].snd) pref[i] = pref[i - 1] + A[i - 1].fst;
		else pref[i] = pref[i - 1] - A[i - 1].fst;
	}
	get(0); get(1);
	dp[0] = 0;
	for (i = 1; i <= A.size(); i++)
	{
		dp[i] = dp[i - 1] + C[i - 1];
		if (nx[i] != -1)
		{
			dp[i] = min(dp[i], dp[nx[i]] + ((A[i - 1].snd) ? (pref[i] - pref[nx[i]]) : (pref[nx[i]] - pref[i])) );
		}
		//cout << i << " " << " " << C[i - 1] << " " << dp[i] << " " << nx[i] << " " << pref[i] - pref[nx[i]] << "\n";
	}
	return dp[A.size()];
}

Compilation message (stderr)

wiring.cpp: In function 'void get(bool)':
wiring.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:33:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while (i < r.size() || j < b.size())
      |         ~~^~~~~~~~~~
wiring.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while (i < r.size() || j < b.size())
      |                         ~~^~~~~~~~~~
wiring.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   int valL = (i < r.size()) ? r[i] : INF;
      |               ~~^~~~~~~~~~
wiring.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   int valR = (j < b.size()) ? b[j] : INF;
      |               ~~^~~~~~~~~~
wiring.cpp:41:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    if (j < b.size()) {C[A.size() - 1] = min(C[A.size() - 1], b[j] - valL);}
      |        ~~^~~~~~~~~~
wiring.cpp:49:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    if (i < r.size()) {C[A.size() - 1] = min(C[A.size() - 1], r[i] - valR);}
      |        ~~^~~~~~~~~~
wiring.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (i = 1; i <= A.size(); i++)
      |              ~~^~~~~~~~~~~
wiring.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (i = 1; i <= A.size(); i++)
      |              ~~^~~~~~~~~~~

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