Submission #296014

#	Time	Username	Problem	Language	Result	Execution time	Memory
296014		Gurban	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	384 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

ll ans;
int del[maxn];
stack<pii>bir,iki;

ll min_total_length(vi r, vi b) {
	vector<pii> v;
	for(auto i : r) v.pb({i,1});
	for(auto i : b) v.pb({i,2});
	sort(all(v));
	
	for(auto i : v) cout<<i.ff<<' ';
	cout<<'\n';
	for(int i = 0;i < sz(v);i++){
		if(v[i].ss==1 and !iki.empty()){
			ans += v[i].ff-iki.top().ff;
			del[i]=del[iki.top().ss]=1;
			iki.pop();
		}
		if(v[i].ss==2 and !bir.empty()){
			ans += v[i].ff-bir.top().ff;
			del[i]=del[bir.top().ss]=1;
			bir.pop();
		}
		if(del[i]==0){
			if(v[i].ss==1) bir.push({v[i].ff,i});
			else iki.push({v[i].ff,i});
		}
	}

	// cout<<ans<<'\n';

	if(sz(b) > sz(r)){
		for(int i = 0;i < sz(v);i++){
			if(del[i]) continue;
			int jog=mod;
			int pos=upper_bound(all(r),v[i].ff)-r.begin();
			if(pos < sz(r)) jog=(r[pos]-v[i].ff);
			pos--;
			if(pos > 0) jog=min(jog,v[i].ff-r[pos]);
			ans+=jog;
		}
	}
	else {
		for(int i = 0;i < sz(v);i++){
			if(del[i]) continue;
			int jog = mod;
			int pos = upper_bound(all(b),v[i].ff)-b.begin();
			if(pos < sz(r)) jog = (b[pos] - v[i].ff);
			pos--;
			if(pos > 0) jog = min(jog,v[i].ff-b[pos]);
			ans+=jog;
		}
	}

	return ans;
}

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