Submission #643125

#	Time	Username	Problem	Language	Result	Execution time	Memory
643125		ymm	Wiring (IOI17_wiring)	C++17	100 / 100	82 ms	10060 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

template<class T>
ll bin(T f, int l, int r)
{
	--r;
	while (l < r) {
		int m = (l+r)/2;
		if (f(m) < f(m+1))
			r = m;
		else
			l = m+1;
	}
	return f(l);
}

const int N = 200'010;
pll a[N];
ll ps[N];
ll dp[N];
int n;

ll get(int i, int p, int j)
{
	int c1 = p - i;
	int c2 = j - p;
	ll x = ps[j] - 2*ps[p] + ps[i] + min(dp[j-1], dp[j]);
	if (c1 > c2)
		return x + a[p].first*(c1-c2);
	else
		return x - a[p-1].first*(c2-c1);
}

long long min_total_length(std::vector<int> R, std::vector<int> B) {
	Loop (i,0,R.size())
		a[i] = {R[i], 0};
	Loop (i,0,B.size())
		a[i+R.size()] = {B[i], 1};
	n = R.size() + B.size();
	sort(a, a+n);
	Loop (i,0,n)
		ps[i+1] = ps[i] + a[i].first;
	Loop (i,0,n)
		a[i].second ^= a[n-1].second;
	dp[n] = 0;
	int i=n-1, lst[2];
	while (0<=i && a[i].second == 0)
		dp[i--] = 1e18;
	lst[0] = i+1;
	while (0<=i && a[i].second == 1) {
		dp[i] = get(i, lst[0], n);
		i--;
	}
	while (0 <= i) {
		if (a[i+1].second != a[i].second)
			lst[a[i+1].second] = i+1;
		dp[i] = bin([&](int k){return get(i, lst[!a[i].second], lst[!a[i].second]+k);}, 1, lst[a[i].second] - lst[!a[i].second]+1);
		--i;
	}
	return dp[0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
wiring.cpp:42:2: note: in expansion of macro 'Loop'
   42 |  Loop (i,0,R.size())
      |  ^~~~
wiring.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
wiring.cpp:44:2: note: in expansion of macro 'Loop'
   44 |  Loop (i,0,B.size())
      |  ^~~~

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