Submission #331012

#	Time	Username	Problem	Language	Result	Execution time	Memory
331012		thecodingwizard	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	238 ms	16108 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update>;

//g++ -std=c++17 -O2 -fsanitize=undefined /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/x86_64-apple-darwin19/bits/stdc++.h
#define maxn 100005
#define mod 1000000007
int n, k;
pair<ll, pair<ll, ll> > interval[maxn]; 
ll ans;


Tree<pair<ll, int> > endpoints;

void setupIO(string s)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
int main()
{
	//setupIO("bridges");
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> k >> n;
	int counter = 0;
	ll pre = 0;
	endpoints.clear();
	for (int i=0; i<n; i++)
	{
		char p, q;
		ll s, t;
		cin >> p >> s >> q >> t;
		if (p == q)
		{
			pre += abs(s - t);
		}
		else
		{
			ll l = min(s, t);
			ll r = max(s, t);
			interval[counter++] = make_pair(s+t, make_pair(l, r));
			pre += r - l + 1;
		}
	}
    sort(interval, interval+counter);
	//use the below version to make it easier to randomly generate test cases 
	// for (int i=0; i<n; i++)
	// {
	// 	ll s, t;
	// 	cin >> s >> t;
	// 	ll l = min(s, t);
	// 	ll r = max(s, t);
	// 	interval[counter++] = make_pair(s+t, make_pair(l, r));
	// 	pre += r - l + 1;
	// }
	n = counter;
	if (k == 1)
	{
		ans = 0;
		//we just want to find the median of the endpoints 
		for (int i=0; i<n; i++)
		{
			endpoints.insert(make_pair(interval[i].second.first, 2*i));
			endpoints.insert(make_pair(interval[i].second.second, 2*i+1));
		}
		ll x = (endpoints.find_by_order(n-1)->first + endpoints.find_by_order(n)->first) / 2;
		cerr << x << endl;
		for (int i=0; i<n; i++)
		{
			ll l = interval[i].second.first; ll r = interval[i].second.second;
			if (l <= x && x <= r)
			{
				continue;
			}
			else if (x < l)
			{
				ans += 2 * (l-x);
			}
			else
			{
				ans += 2 * (x-r);
			} 
		}
	}
	else
	{
		ans = LLONG_MAX;
		sort(interval, interval+n); //sorted in order of increasing midpoint
		for (int i=0; i<n-1; i++)
		{
			//things 0 to i take the first bridge, i+1 to n-1 take the second bridge
			endpoints.clear();
			for (int j=0; j<=i; j++)
			{
				endpoints.insert(make_pair(interval[j].second.first, 2*j));
				endpoints.insert(make_pair(interval[j].second.second, 2*j+1));
			}
			ll x = (endpoints.find_by_order(i)->first + endpoints.find_by_order(i+1)->first) / 2;
			endpoints.clear();
			for (int j=i+1; j<n; j++)
			{
				endpoints.insert(make_pair(interval[j].second.first, 2*j));
				endpoints.insert(make_pair(interval[j].second.second, 2*j+1));
			}
			ll y = (endpoints.find_by_order(n-i-2)->first + endpoints.find_by_order(n-i-1)->first) / 2;

			ll temp = 0;
			for (int j=0; j<=i; j++)
			{
				ll l = interval[j].second.first; ll r = interval[j].second.second;
				if (l <= x && x <= r)
				{
					continue;
				}
				else if (x < l)
				{
					temp +=  2 * (l-x);
				}
				else
				{
					temp += 2 * (x-r);
				}
			}
			//cerr << temp << endl;
			for (int j=i+1; j<n; j++)
			{
				ll l = interval[j].second.first; ll r = interval[j].second.second;
				if (l <= y && y <= r)
				{
					continue;
				}
				else if (y < l)
				{
					temp += 2 * (l-y);
				}
				else
				{
					temp += 2 * (y-r);
				}
			}
			//cerr << temp << endl;
			ans = min(ans, temp);
		}
	}
	cout << ans + pre << endl;
}

Compilation message (stderr)

bridge.cpp: In function 'void setupIO(std::string)':
bridge.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37