Submission #1002978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002978		ThegeekKnight16	Izvanzemaljci (COI21_izvanzemaljci)	C++17	0 / 100	3082 ms	604 KiB

izvanzemaljci

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;


void solve1(int N, int K)
{
	int x11 = INF, x12 = 0, y11 = INF, y12 = 0;
	for (int i = 0; i < N; i++)
	{
		int X, Y;
		cin >> X >> Y;
		x11 = min(x11, X);
		x12 = max(x12, X);
		y11 = min(y11, Y);
		y12 = max(y12, Y);
	}

	int l = max(x12 - x11, y12 - y11);
	cout << x11 << " " << y11 << " " << l << '\n';
}
void solve2(int N, int K)
{

}

void bt(int id, tuple<int, int, int, int> q1, tuple<int, int, int, int> q2, tuple<int, int, int, int> q3, int &resp, vector<tuple<int, int, int>> &ans, const vector<pair<int, int>> &v)
{
	if (id == v.size())
	{
		auto [x11, x12, y11, y12] = q1;
		auto [x21, x22, y21, y22] = q2;
		auto [x31, x32, y31, y32] = q3;
		if (x11 > x12) x11 = -INF, x12 = -INF+1, y11 = -INF, y12 = -INF+1;
		if (x21 > x22) x21 = INF, x22 = INF+1, y21 = -INF, y22 = -INF+1;
		if (x31 > x32) x31 = INF, x32 = INF+1, y31 = INF, y32 = INF+1;
		int l1 = max(x12 - x11, y12 - y11); x12 = x11 + l1, y12 = y11 + l1;
		int l2 = max(x22 - x21, y22 - y21); x22 = x21 + l2, y22 = y21 + l2;
		int l3 = max(x32 - x31, y32 - y31); x32 = x31 + l3, y32 = y31 + l3;
		if (max({l1, l2, l3}) > resp) return;
		bool interX12 = (min(x11, x21) <= max(x11, x21) && max(x11, x21) <= min(x12, x22)) || (min(x11, x21) <= min(x12, x22) && min(x12, x22) <= max(x11, x21));
		bool interX13 = (min(x11, x31) <= max(x11, x31) && max(x11, x31) <= min(x12, x32)) || (min(x11, x31) <= min(x12, x32) && min(x12, x32) <= max(x11, x31));
		bool interX23 = (min(x21, x31) <= max(x21, x31) && max(x21, x31) <= min(x21, x32)) || (min(x21, x31) <= min(x22, x32) && min(x22, x32) <= max(x21, x31));
		bool interY12 = (min(y11, y21) <= max(y11, x21) && max(y11, y21) <= min(y12, x22)) || (min(y11, y21) <= min(y12, y22) && min(y12, y22) <= max(y11, y21));
		bool interY13 = (min(y11, y31) <= max(y11, x31) && max(y11, y31) <= min(y12, x32)) || (min(y11, y31) <= min(y12, y32) && min(y12, y32) <= max(y11, y31));
		bool interY23 = (min(y21, y31) <= max(y21, x31) && max(y21, y31) <= min(y21, x32)) || (min(y21, y31) <= min(y22, y32) && min(y22, y32) <= max(y21, y31));
		if (interX12 && interY12) return;
		if (interX13 && interY13) return;
		if (interX23 && interY23) return;
		resp = max({l1, l2, l3});
		ans[0] = make_tuple(x11, y11, l1);
		ans[1] = make_tuple(x21, y21, l2);
		ans[2] = make_tuple(x31, y31, l3);
		return;
	}

	auto [x11, x12, y11, y12] = q1;
	auto [x21, x22, y21, y22] = q2;
	auto [x31, x32, y31, y32] = q3;
	
	auto [X, Y] = v[id];
	bt(id+1, make_tuple(min(x11, X), max(x12, X), min(y11, Y), max(y12, Y)), q2, q3, resp, ans, v);
	bt(id+1, q1, make_tuple(min(x21, X), max(x22, X), min(y21, Y), max(y22, Y)), q3, resp, ans, v);
	bt(id+1, q1, q2, make_tuple(min(x31, X), max(x32, X), min(y31, Y), max(y32, Y)), resp, ans, v);	
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, K;
	cin >> N >> K;
	if (K == 1) {solve1(N, K); return 0;}
	else if (K == 2) {solve2(N, K); return 0;}

	vector<pair<int, int>> v(N); for (auto &[x, y] : v) cin >> x >> y;
	int resp = INF; vector<tuple<int, int, int>> ans(3);
	bt(0, make_tuple(INF, 0, INF, 0), make_tuple(INF, 0, INF, 0), make_tuple(INF, 0, INF, 0), resp, ans, v);
	for (auto x : ans)
		cout << get<0>(x) << " " << get<1>(x) << " " << get<2>(x) << '\n';
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'void bt(int, std::tuple<int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int, int>, int&, std::vector<std::tuple<int, int, int> >&, const std::vector<std::pair<int, int> >&)':
izvanzemaljci.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if (id == v.size())
      |      ~~~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32