Submission #296057

#	Time	Username	Problem	Language	Result	Execution time	Memory
296057		Dovran	Wiring (IOI17_wiring)	C++11	0 / 100	1 ms	384 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

#define N 100009
#define pii pair <int, int>
#define ff first
#define ss second
#define sz() size()
#define pb push_back
#define ll long long

using namespace std;

ll ans;

ll min_total_length(vector<int>a, vector<int>b){
	ll n=a.sz();
	ll m=b.sz();
	ll x=0, y=0;
	map<int, int>vis;
	vector<pii>e;
	for(auto i:a)
		e.pb({i, 0});
	for(auto i:b)
		e.pb({i, 1});
	sort(e.begin(), e.end());
	for(int i=0; i<e.sz(); i++){
		if(vis[e[i].ff])
			continue;
		int l=i, r=i;
		while(l>=0){
			if(e[l].ss!=e[i].ss and !vis[e[l].ff])
				break;
			l--;
		}
		while(r<e.sz()){
			if(e[r].ss!=e[i].ss and !vis[e[r].ff])
				break;
			r++;
		}
		int x=-1;
		if(l>=0)
			x=l;
		if(r<e.sz() and (x<0 or e[i].ff-e[x].ff > e[r].ff-e[i].ff))
			x=r;
//		cout<<e[i].ff<<' '<<l<<' '<<e[l].ff<<" - "<<r<<' '<<e[r].ff<<" --> ";
		if(x!=-1){
			vis[e[i].ff]=1;
			vis[e[x].ff]=1;
			ans+=abs(e[i].ff-e[x].ff);
		}
//		cout<<ans<<'\n';
	}
//	cout<<ans<<'\n';
	for(int i=0; i<e.sz(); i++){
		if(!vis[e[i].ff]){
			int l=i, r=i;
			while(l>0){
				if(e[l].ss!=e[i].ss)
					break;
				l--;
			}
			while(r<e.sz()){
				if(e[r].ss!=e[i].ss)
					break;
				r++;
			}
			int x=-1;
			if(l>=0)
				x=l;
			if(r<e.sz() and (x<0 or e[i].ff-e[x].ff > e[r].ff-e[i].ff))
				x=r;
			vis[e[i].ff]=1;
			ans+=abs(e[i].ff-e[x].ff);
		}
	}
	return ans;
}
/*
int main(){
	int n, m, x;
	vector<int>a, b;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		cin>>x, a.pb(x);
	for(int i=1; i<=m; i++)
		cin>>x, b.pb(x);
	
	cout<<min_total_length(a, b);
}*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0; i<e.sz(); i++){
      |                ^
wiring.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while(r<e.sz()){
      |          ^
wiring.cpp:44:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(r<e.sz() and (x<0 or e[i].ff-e[x].ff > e[r].ff-e[i].ff))
      |       ^
wiring.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0; i<e.sz(); i++){
      |                ^
wiring.cpp:63:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    while(r<e.sz()){
      |           ^
wiring.cpp:71:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    if(r<e.sz() and (x<0 or e[i].ff-e[x].ff > e[r].ff-e[i].ff))
      |        ^
wiring.cpp:17:5: warning: unused variable 'n' [-Wunused-variable]
   17 |  ll n=a.sz();
      |     ^
wiring.cpp:18:5: warning: unused variable 'm' [-Wunused-variable]
   18 |  ll m=b.sz();
      |     ^
wiring.cpp:19:5: warning: unused variable 'x' [-Wunused-variable]
   19 |  ll x=0, y=0;
      |     ^
wiring.cpp:19:10: warning: unused variable 'y' [-Wunused-variable]
   19 |  ll x=0, y=0;
      |          ^

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