Submission #1295349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295349		danirasilla	Izvanzemaljci (COI21_izvanzemaljci)	C++20	Compilation error	0 ms	0 KiB

izvanzemaljci

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <random>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <stack>
#include <numeric>
#include <deque>

#define int long long


using namespace std;
typedef long long ll;
typedef long double ld;
const ll md1 = 1'000'000'000;
const ll md2 = 998244353;
const ll mdd = 666013;

vector<pair<pair<int, int>, int>> cdombi(vector<pair<pair<int, int>, int>>& a, vector<pair<pair<int, int>, int>>& b) {
	if (max(a[0].second, a[1].second) > max(b[0].second, b[1].second))
		return b;
	return a;
}

vector<pair<int, int>> a;
vector<pair<pair<int, int>, int>> getans;

bool check2(int l, int r, int k, int bou) {
	vector<pair<int, int>> an(r - l);
	for (int i = l; i < r; i++)
		an[i - l] = a[i];
	if (r - l == 1) {
		getans[0] = { {an[0].first, an[0].second}, 1 };
		getans[1] = { {md1 + 5, md1 + 5}, 1 };
		return true;
	}

	for (int II = 0; II < 2; II++) {
		vector<int> sx(r - l), sn(r - l);
		sx[r - l - 1] = an[r - l - 1].second;
		sn[r - l - 1] = an[r - l - 1].second;
		for (int i = r - l - 2; i > -1; i--) {
			sn[i] = min(sn[i + 1], an[i].second);
			sx[i] = max(sx[i + 1], an[i].second);
		}
		int mn = an[0].second;
		int mx = an[0].second;
		for (int i = 1; i < r - l; i++) {
			if (an[i - 1].first != an[i].first && an[i - 1].first - an[0].first <= k && mx - mn <= k && an[r - l - 1].first - an[i].first <= k && sx[i] - sn[i] <= k) {
				getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
				getans[1] = { {an[i].first, sn[i]}, k };
				if (!II) {
					if (an[i].first - 2 - bou < k)
						continue;
					getans[0].first.first = min(an[0].first, an[i].first - 1 - k);
				}
				if (II) {
					swap(getans[0].first.first, getans[0].first.second);
					swap(getans[1].first.first, getans[1].first.second);
				}
				return true;
			}
			mn = min(mn, an[i].second);
			mx = max(mx, an[i].second);
		}

		for (int i = 0; i < r - l; i++)
			swap(an[i].first, an[i].second);
		sort(an.begin(), an.end());
	}
	return false;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	//cin >> t;
	while (t--) {

		int n, k;
		cin >> n >> k;
		a.resize(n);
		getans.resize(k);
		for (int i = 0; i < n; i++)
			cin >> a[i].first >> a[i].second;

		vector<int> xa(k, md1 + 1), ya(k, md1 + 1), l(k, 1);
		int ans = md1 * 2;
		l[0] = ans;
		xa[0] = -md1;
		ya[0] = -md1;
		for (int i = 1; i < k; i++)
			xa[i] = md1 + i * 2, ya[i] = md1 + 2 * i;

		for (int II = 0; II < 4; II++) {
			sort(a.begin(), a.end());

			vector<pair<pair<int, int>, int>> sufk1(n);
			sufk1[n - 1] = { {a[n - 1].first, a[n - 1].second }, 1 };
			{
				int mx = a[n - 1].first, nx = a[n - 1].first, my = a[n - 1].second, ny = a[n - 1].second;
				for (int i = n - 2; i > -1; i--) {
					mx = max(mx, a[i].first);
					nx = min(nx, a[i].first);
					my = max(my, a[i].second);
					ny = min(ny, a[i].second);
					sufk1[i] = { {nx, ny}, max(mx - nx, my - ny) };
				}
			}
			if (ans > sufk1[0].second) {
				ans = sufk1[0].second;
				l[0] = sufk1[0].second;
				xa[0] = sufk1[0].first.first;
				ya[0] = sufk1[0].first.second;
				for (int i = 1; i < k; i++)
					l[i] = 1, xa[i] = md1 + 2 * i, ya[i] = md1 + 2 * i;
			}

			if (k >= 2) {
				int ll = 0;
				int rr = ans;
				vector<pair<pair<int, int>, int>> anss(k);
				for (int i = 0; i < k; i++)
					anss[i] = { {xa[i], ya[i]}, l[i] };
				while (ll + 1 < rr) {
					int md = (ll + rr) / 2;

					bool ok = false;
					if (k == 2) {
						if (check2(0, n, md, -md1 * 2 - 1)) {
							ok = true;
							anss[0] = getans[0];
							anss[1] = getans[1];
						}
					}
					else {
						int xn = a[0].first, xx = a[0].first, yn = a[0].second, yx = a[0].second;
						int po = 0;
						while (po < n && xx - xn <= k && yx - yn <= k) {
							xn = min(xn, a[po].first);
							xx = max(xx, a[po].first);
							yn = min(yn, a[po].second);
							yx = max(yx, a[po].second);
							po++;
						}
						po--;
						if (check2(po, n, md, a[po - 1].first)) {
							ok = true;
							anss[0] = getans[0];
							anss[1] = getans[1];
							anss[2] = { { xn, yn}, md };
						}
					}
					if (ok)
						rr = md;
					else
						ll = md;
				}
				if (rr < ans)
					for (int i = 0; i < k; i++) {
						ans = rr;
						l[i] = anss[i].second;
						xa[i] = anss[i].first.first;
						ya[i] = anss[i].first.second;
					}
			}

			for (int i = 0; i < n; i++)
				a[i] = { a[i].second, -a[i].first };
			for (int i = 0; i < k; i++) {
				int tp = xa[i] + l[i];
				xa[i] = ya[i];
				ya[i] = -tp;
			}
		}
		for (int i = 0; i < k; i++)
			cout << xa[i] << " " << ya[i] << " " << l[i] << "\n";
	}
	return 0;
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'bool check2(long long int, long long int, long long int, long long int)':
izvanzemaljci.cpp:58:77: error: no matching function for call to 'max(int, const long long int&)'
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/string:51,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from izvanzemaljci.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:58:77: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:58:77: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from izvanzemaljci.cpp:3:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:58:77: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:58:77: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:58:126: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<std::pair<long long int, long long int>, long long int> >, std::pair<std::pair<long long int, long long int>, long long int> >::value_type' {aka 'std::pair<std::pair<long long int, long long int>, long long int>'} and '<brace-enclosed initializer list>')
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                                                                              ^
In file included from /usr/include/c++/13/bits/stl_algobase.h:64:
/usr/include/c++/13/bits/stl_pair.h:439:9: note: candidate: 'template<class _U1, class _U2> constexpr std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) requires  _S_assignable<const _U1&, const _U2&>() [with _U2 = _U1; _T1 = std::pair<long long int, long long int>; _T2 = long long int]'
  439 |         operator=(const pair<_U1, _U2>& __p)
      |         ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:439:9: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:58:126: note:   couldn't deduce template parameter '_U1'
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                                                                              ^
/usr/include/c++/13/bits/stl_pair.h:451:9: note: candidate: 'template<class _U1, class _U2> constexpr std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) requires  _S_assignable<_U1, _U2>() [with _U2 = _U1; _T1 = std::pair<long long int, long long int>; _T2 = long long int]'
  451 |         operator=(pair<_U1, _U2>&& __p)
      |         ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:451:9: note:   template argument deduction/substitution failed:
izvanzemaljci.cpp:58:126: note:   couldn't deduce template parameter '_U1'
   58 |                                 getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
      |                                                                                                                              ^
/usr/include/c++/13/bits/stl_pair.h:416:7: note: candidate: 'constexpr std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(const std::pair<_T1, _T2>&) requires  _S_assignable<const _T1&, const _T2&>() [with _T1 = std::pair<long long int, long long int>; _T2 = long long int]'
  416 |       operator=(const pair& __p)
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:416:29: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::pair<std::pair<long long int, long long int>, long long int>&'
  416 |       operator=(const pair& __p)
      |                 ~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_pair.h:427:7: note: candidate: 'constexpr std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::pair<_T1, _T2>&&) requires  _S_assignable<_T1, _T2>() [with _T1 = std::pair<long long int, long long int>; _T2 = long long int]'
  427 |       operator=(pair&& __p)
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:427:24: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::pair<std::pair<long long int, long long int>, long long int>&&'
  427 |       operator=(pair&& __p)
      |                 ~~~~~~~^~~