Submission #1046823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046823		pcc	Wiring (IOI17_wiring)	C++17	100 / 100	45 ms	19508 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define sc second
#define int ll

const ll inf = 1e18;
const int mxn = 2e5+10;
ll dp[mxn];
vector<vector<int>> gp;
vector<pll> v;

void calc(vector<int> pre,vector<int> tar){
	//cerr<<"CALC: "<<endl;for(auto &i:pre)cerr<<i<<',';cerr<<endl;for(auto &i:tar)cerr<<i<<',';cerr<<endl;
	vector<ll> p1,p2;
	reverse(pre.begin(),pre.end());
	p1.resize(pre.size());
	for(int i = 0;i<pre.size();i++){
		p1[i] = v[pre[i]].fs;
		if(i)p1[i] += p1[i-1];
	}
	p2.resize(tar.size());
	for(int i = 0;i<tar.size();i++){
		p2[i] = v[tar[i]].fs;
		if(i)p2[i] += p2[i-1];
	}

	priority_queue<pll,vector<pll>,greater<pll>> pq;
	pq.push(pll(inf,inf));
	ll rp = inf;
	ll sum = 0;
	ll maxl = v[pre[0]].fs;
	ll minr = v[tar[0]].fs;

	for(int i = 0;i<pre.size();i++){
		int pos = pre[i];
		ll tmp = min(dp[pos],dp[pos-1])-p1[i]+minr*(i+1);
		pq.push(pll(tmp,i+1));
	}

	for(int i = 0;i<tar.size();i++){
		while(!pq.empty()&&pq.top().sc<i+1){
			int id = pq.top().sc-1;
			pq.pop();
			int pos = pre[id];
			ll tmp = min(dp[pos],dp[pos-1])-p1[id]+maxl*(id+1);
			rp = min(rp,tmp);
		}
		int pos = tar[i];
		ll t1 = pq.top().fs-minr*(i+1)+p2[i];
		ll t2 = rp-maxl*(i+1)+p2[i];
		dp[pos] = min(t1,t2);
	}
	return;

}

long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
	v.push_back(pii(-1,-1));
	for(auto &i:r)v.push_back(pii(i,0));
	for(auto &i:b)v.push_back(pii(i,1));
	sort(v.begin(),v.end());
	//for(auto &i:v)cerr<<i.sc<<',';cerr<<endl;
	for(int i = 0;i<v.size();i++){
		if(gp.empty()||v[gp.back().back()].sc != v[i].sc)gp.push_back(vector<int>(1,i));
		else gp.back().push_back(i);
	}
	/*
	cerr<<"GPS: "<<endl;for(auto &i:gp){
		for(auto &j:i)cerr<<j<<',';cerr<<endl;
	}cerr<<endl;
	*/
	fill(dp,dp+mxn,inf);
	dp[0] = 0;
	for(int i = 2;i<gp.size();i++){
		auto pre = gp[i-1],now = gp[i];
		calc(pre,now);
	}
	//for(int i = 0;i<v.size();i++)cerr<<dp[i]<<' ';cerr<<endl;
	return dp[v.size()-1];
}

Compilation message (stderr)

wiring.cpp: In function 'void calc(std::vector<long long int>, std::vector<long long int>)':
wiring.cpp:22:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0;i<pre.size();i++){
      |                ~^~~~~~~~~~~
wiring.cpp:27:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0;i<tar.size();i++){
      |                ~^~~~~~~~~~~
wiring.cpp:39:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0;i<pre.size();i++){
      |                ~^~~~~~~~~~~
wiring.cpp:45:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0;i<tar.size();i++){
      |                ~^~~~~~~~~~~
wiring.cpp:35:5: warning: unused variable 'sum' [-Wunused-variable]
   35 |  ll sum = 0;
      |     ^~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:68:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~
wiring.cpp:79:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i = 2;i<gp.size();i++){
      |                ~^~~~~~~~~~

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