Submission #264029

#	Time	Username	Problem	Language	Result	Execution time	Memory
264029		kshitij_sodani	Wiring (IOI17_wiring)	C++14	13 / 100	95 ms	12920 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second



#include "wiring.h"

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n,m;
	n=r.size();
	m=b.size();
	llo ans=0;
/*	if(r[n-1]<b[0]){
		
		for(int i=0;i<min(n,m);i++){
			ans+=b[i]-r[i];
		}
		for(int i=min(n,m);i<n;i++){
			ans+=b[0]-r[i];
		}
		for(int i=min(n,m);i<m;i++){
			ans+=b[i]-r[n-1];
		}
		return ans;
	}
	else{*/
		queue<int> aa;
		queue<int> bb;
		vector<pair<int,int>> cc;
		for(auto j:r){
			cc.pb({j,0});
		}
		for(auto j:b){
			cc.pb({j,1});
		}
		sort(cc.begin(),cc.end());
		for(auto j:cc){
			
			if(j.b==0){
				if(bb.size()==0){
					aa.push(j.a);
					continue;
				}
				int x=bb.front();
				bb.pop();
				ans+=j.a-x;
			}
			else{
				if(aa.size()==0){
					bb.push(j.a);
					continue;
				}
				int x=aa.front();
				aa.pop();
				ans+=j.a-x;
			}
		//	cout<<j.a<<":"<<j.b<<":"<<ans<<endl;
			
		}


		set<int> mi;
		set<int> ma;
		for(auto j:r){
			mi.insert(j);
		}
		for(auto j:b){
			ma.insert(j);
		}
		while(aa.size()){
			int x=aa.front();
			aa.pop();
			auto j=ma.lower_bound(x);
			int cur=1e9;
			if(j!=ma.end()){
				cur=min(cur,abs((*j)-x));
			}
			if(j!=ma.begin()){
				j--;
				cur=min(cur,abs((*j)-x));
			}
			ans+=cur;
		}
		while(bb.size()){
			int x=bb.front();
			bb.pop();
			auto j=mi.lower_bound(x);
			int cur=1e9;
			if(j!=mi.end()){
				cur=min(cur,abs((*j)-x));
			}
			if(j!=mi.begin()){
				j--;
				cur=min(cur,abs((*j)-x));
			}
			ans+=cur;
		}
		return ans;
	/*}
*/



	/*vector<int> rr;
	vector<int> bb;
	while(r.size() or b.size()){
		for(auto i:r){
			for(auto j:b){



			}
		}
	}


*/








	return ans;
}




/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	return 0;
}
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:14:6: warning: variable 'n' set but not used [-Wunused-but-set-variable]
   14 |  int n,m;
      |      ^
wiring.cpp:14:8: warning: variable 'm' set but not used [-Wunused-but-set-variable]
   14 |  int n,m;
      |        ^

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