Submission #703733

#	Time	Username	Problem	Language	Result	Execution time	Memory
703733		600Mihnea	Palembang Bridges (APIO15_bridge)	C++17	Compilation error	0 ms	0 KiB

bridge

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

#define int long long 

const int INF = (int)1e18 + 7;

pair<int, int> _rd_()
{
	string s;
	int i;
	cin >> s >> i;
	assert(s == "A" || s == "B");
	return { s == "B", i };
}

const int N = (int)1e5 + 7;
int k;
int n;
int extra;
pair<int, int> c1[N], c2[N];

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	cin >> k >> n;
	{
		int y = 0;
		for (int i = 1; i <= n; i++)
		{
			c1[i] = _rd_();
			c2[i] = _rd_();
			if (c1[i].first == c2[i].first)
			{
				extra += abs(c1[i].second - c2[i].second);
				continue;
			}
			y++;
			c1[y] = c1[i];
			c2[y] = c2[i];
		}
		n = y;
	}
	if (n == 0)
	{
		cout << extra << "\n";
		return 0;
	}
	if (k == 1)
	{
		vector<int> coords;
		for (int i = 1; i <= n; i++)
		{
			coords.push_back(c1[i].second);
			coords.push_back(c2[i].second);
		}
		nth_element(coords.begin(), coords.begin() + n - 1, coords.end());
		int su = 0;
		for (int i = 0; i < 2 * n; i++)
		{
			su += abs(coords[i] - coords[n - 1]);
		}
		cout << su + extra + n << "\n";
		return 0;
	}
	assert(k == 2);
	set<int> s;
	for (int i = 1; i <= n; i++)
	{
		s.insert(c1[i].second);
		s.insert(c2[i].second);
		if (c1[i].second > c2[i].second)
		{
			swap(c1[i], c2[i]);
		}
	}
	vector<pair<int, int>> segs;
	for (int i = 1; i <= n; i++)
	{
		segs.push_back({ c1[i].second, c2[i].second });
	}
	vector<int> co;
	for (auto& x : s)
	{
		co.push_back(x);
	}
	assert(!co.empty());
	co.push_back(co.back());
	assert((int)co.size() >= 2);
	vector<int> coords;
	for (int i = 1; i <= n; i++)
	{
		coords.push_back(c1[i].second);
		coords.push_back(c2[i].second);
	}
	sort(coords.begin(), coords.begin() + n - 1, coords.end());
	int sol = INF;
	for (int px = 0; px < (int)co.size(); px++)
	{
		for (int py = 0; py < (int)co.size(); py++)
		{
			int x = co[px];
			x = coords[n - 1];
			int y = co[py];
			int cur = 0;
			for (auto& s : segs)
			{
				if (s.first <= x && x <= s.second)
				{
					continue;
				}
				if (s.first <= y && y <= s.second)
				{
					continue;
				}
				cur += min({ abs(s.first - x), abs(s.first - y), abs(s.second - x), abs(s.second - y) });
			}
			sol = min(sol, cur);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		extra += abs(c1[i].second - c2[i].second);
	}
	cout << 2 * sol + extra + n << "\n";
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from bridge.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Iterator2 = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]'
bridge.cpp:126:59:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: no match for call to '(__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >) (long long int&, long long int&)'
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = long long int; _Iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]'
bridge.cpp:126:59:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: no match for call to '(__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >) (long long int&, long long int&)'
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Value = long long int; _Compare = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Distance = long int; _Tp = long long int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Distance = long int; _Tp = long long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _Compare = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]'
bridge.cpp:126:59:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: no match for call to '(__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >) (long long int&, long long int&)'
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~