Submission #79111

#	Time	Username	Problem	Language	Result	Execution time	Memory
79111		Plurm	Wiring (IOI17_wiring)	C++11	0 / 100	2 ms	508 KiB

wiring

#include "wiring.h"
#include <vector>
#include <algorithm>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
	vector<pair<int,bool> > combined;
	vector<long long> qs;
	for(int x : r){
		combined.emplace_back(x,false);
	}
	for(int x : b){
		combined.emplace_back(x,true);
	}
	sort(combined.begin(),combined.end());
	bool cur = !combined.front().second;
	int clen = 0;
	int llen = 0;
	int begin = 0;
	vector<int> lpos;
	lpos.resize(combined.size());
	vector<int> laxis;
	laxis.resize(combined.size());
	for(int i = 0; i < combined.size(); i++){
		if(combined[i].second == cur){
			clen++;
		}else{
			begin = i;
			llen = clen;
			clen = 1;
			cur = !cur;
		}
		lpos[i] = 2*begin-i-1;
		laxis[i] = begin;
		if(lpos[i] < begin-llen){
			lpos[i] = -1;
		}
	}
	qs.push_back(combined.front().first);
	for(int i = 1; i < combined.size(); i++){
		qs.push_back(qs.back() + (long long)combined[i].first);
	}
	vector<long long> dp;
	dp.resize(combined.size());
	for(int i = 1; i < combined.size(); i++){
		// Case 1: dp[i] = dp[i-1] + abs(pos[i] - pos[j])
		if(combined[i].second){
			auto it = lower_bound(r.begin(),r.end(),combined[i].first);
			if(it == r.begin()){
				dp[i] = 1e18;
			}else{
				dp[i] = dp[i-1] + combined[i].first - *(it-1);
				if(it != r.end())
					dp[i] = min(dp[i],dp[i-1] + *it - combined[i].first);
			}
		}else{
			auto it = lower_bound(b.begin(),b.end(),combined[i].first);
			if(it == b.begin()){
				dp[i] = 1e18;
			}else{
				dp[i] = dp[i-1] + combined[i].first - *(it-1);
				if(it != b.end())
					dp[i] = min(dp[i],dp[i-1] - combined[i].first + *it);
			}
		}
		// Case 2: dp[i] = dp[j] + Distance Differences
		if(lpos[i] != -1){
			dp[i] = min(dp[i],qs[i] - qs[laxis[i]-1] - qs[laxis[i]-1] + qs[lpos[i]-1] + dp[lpos[i]-1]);
		}
	}
	return dp.back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < combined.size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < combined.size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < combined.size(); i++){
                 ~~^~~~~~~~~~~~~~~~~

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