Submission #73181

#	Time	Username	Problem	Language	Result	Execution time	Memory
73181		KieranHorgan	Wiring (IOI17_wiring)	C++17	100 / 100	361 ms	114864 KiB

wiring

#pragma GCC optimize("O3")
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int n, m, ans;
vector<int> fullList;
unordered_map<int, bool> isRed, isBlue;
vector<vector<int>> segments;
vector<vector<int>> prefixR;
vector<vector<int>> prefixL;
 
int calcWire(int s, int l, int r) {
	int res = 0;
	res += prefixL[s][l];
	res += (segments[s].size()-l) * (segments[s+1][0]-segments[s].back());
	res += prefixR[s+1][r];
	res += (r+1) * (segments[s+1][0]-segments[s].back());
	res -= min((int)segments[s].size()-l, r+1)*(segments[s+1][0]-segments[s].back());
	return res;
}
 
int shash(int a, int b) {
	return a*1000000 + b;
}
unordered_map<int, int> dp;
 
long long min_total_length(vector<signed> r, vector<signed> b) {
	dp.reserve(32768); dp.max_load_factor(0.25);
	n = r.size();
	m = b.size();
	fullList.resize(n+m);
	merge(r.begin(), r.end(), b.begin(), b.end(), fullList.begin());
	for(auto x: r)
		isRed[x]=1;
	for(auto x: b)
		isBlue[x]=1;
 
	for(int i = 0; i < m+n; i++) {
		if(i==0 || isRed[fullList[i]] != isRed[fullList[i-1]]) {
			segments.push_back(vector<int>(0));
			prefixL.push_back(vector<int>(0));
			prefixR.push_back(vector<int>(0));
			segments.back().push_back(fullList[i]);
		} else {
			segments.back().push_back(fullList[i]);
		}
	}
 
	for(int s = 0; s < segments.size(); s++) {
		prefixR[s].push_back(0);
		for(int i = 1; i < segments[s].size(); i++)
			prefixR[s].push_back(prefixR[s][i-1]+segments[s][i]-segments[s][0]);
		reverse(segments[s].begin(), segments[s].end());
		prefixL[s].push_back(0);
		for(int i = 1; i < segments[s].size(); i++)
			prefixL[s].push_back(prefixL[s][i-1]+segments[s][0]-segments[s][i]);
		reverse(prefixL[s].begin(), prefixL[s].end());
		reverse(segments[s].begin(), segments[s].end());
	}
 
	for(int j = 0; j < segments[1].size(); j++) {
		dp[shash(1,j)] = calcWire(0, 0, j);
	}
	
	for(int s = 2; s < segments.size(); s++) {
		for(int i = 0; i < segments[s].size(); i++) {
			dp[shash(s, i)] = dp[shash(s-1, 0)] + calcWire(s-1, 0, i);
			if(dp[shash(s-2, segments[s-2].size()-1)] != 0)
				dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-2, segments[s-2].size()-1)] + calcWire(s-1, 0, i));
			int lo = 1, hi = max(1ll,(int)segments[s-1].size()-1), j, m1, m2, r1, r2;
			while(lo+1 < hi) {
				m1 = (lo+hi)/2;
				r1 = dp[shash(s-1, m1-1)] + calcWire(s-1, m1, i);
				m2 = m1+1;
				r2 = dp[shash(s-1, m2-1)] + calcWire(s-1, m2, i);
				if(r1==r2)
					lo = m1, hi = m2;
				else if(r1 < r2)
					hi = m2-1;
				else
					lo = m1+1;
			}
			dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-1, lo-1)] + calcWire(s-1, lo, i));
			dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-1, hi-1)] + calcWire(s-1, hi, i));
			// cerr << s << " " << i << ": " << dp[shash(s, i)] << endl;
		}
	}
 
 
	return dp[shash(segments.size()-1, segments.back().size()-1)];
	if(segments.size() == 2)
		return calcWire(0, 0, m-1);
	return -1;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int s = 0; s < segments.size(); s++) {
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < segments[s].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < segments[s].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < segments[1].size(); j++) {
                 ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int s = 2; s < segments.size(); s++) {
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < segments[s].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:72:59: warning: unused variable 'j' [-Wunused-variable]
    int lo = 1, hi = max(1ll,(int)segments[s-1].size()-1), j, m1, m2, r1, r2;
                                                           ^

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