Submission #411906

#	Time	Username	Problem	Language	Result	Execution time	Memory
411906		kai824	Wiring (IOI17_wiring)	C++17	13 / 100	53 ms	9384 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>
#define mp make_pair
#define f first
#define s second

#define deb(x) ; //cerr<<x<<'\n';
#define debl(label,x) ; //cerr<<label<<": "<<x<<'\n';

ll min_total_length(vector<int> r,vector<int> b){//r and b are sorted
	ll ans=0,it=0;
	vector<int> mm;//min cost for each b...
	if(r.size()>b.size())swap(b,r);
	priority_queue<pii,vector<pii>,greater<pii> > pq1,pq2;//pq1 for decreasing, pq2 for increasing
	//value at 0, point of turn
	for(int i=0;i<b.size();i++){
		int x=b[i];
		while(it+1<r.size() && abs(x-r[it])>=abs(x-r[it+1])){
			it++;
		}
		mm.push_back(abs(x-r[it]));
		ans+=mm.back();
		pq1.emplace(x-mm.back(),i);
	}
	it=0;//next point to insert to pq2
	for(int i=0;i<r.size();(i++)){
		while(it<b.size() && b[it]<=r[i]){
			pq2.emplace(-b[it]-mm[it],it);//it kinda not needed but wtv
			it++;
			deb("Converted")
		}
		while(!pq1.empty() && pq1.top().s<it)pq1.pop();
		if(pq1.empty()){
			deb("path 1")
			ans+=pq2.top().f+r[i];
			pq2.pop();continue;
		}
		if(pq2.empty()){
			deb("path 2")
			ans+=pq1.top().f-r[i];
			pq1.pop();
			continue;
		}
		if(pq1.top().f-r[i]>=pq2.top().f+r[i]){//if upward sloping stuff is smaller, just take them
			deb("path 3a")
			ans+=pq2.top().f+r[i];pq2.pop();
		}else if(pq1.size()>=r.size()-i){//enough pq2 stuff for the rest...
			deb("path 3b")
			ans+=pq1.top().f-r[i];pq1.pop();
		}else{
			deb("path 3c")
			ans+=pq2.top().f+r[i];pq2.pop();
		}
	}
	return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<b.size();i++){
      |              ~^~~~~~~~~
wiring.cpp:21:13: 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]
   21 |   while(it+1<r.size() && abs(x-r[it])>=abs(x-r[it+1])){
      |         ~~~~^~~~~~~~~
wiring.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0;i<r.size();(i++)){
      |              ~^~~~~~~~~
wiring.cpp:30:11: 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]
   30 |   while(it<b.size() && b[it]<=r[i]){
      |         ~~^~~~~~~~~

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