제출 #420883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420883		Berted	Izvanzemaljci (COI21_izvanzemaljci)	C++14	38 / 100	3074 ms	9796 KiB

izvanzemaljci

#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#define int long long
#define pii pair<int, int>
#define ppi pair<pii, int>
#define ppp pair<pii, pii>
#define fst first
#define snd second

using namespace std;

const int INF = 1e9 + 7;

int N, K;
vector<pii> A;
pii B[100001];

ppi sqr;
pii prefMin[100001], sufMin[100001];
pii prefMax[100001], sufMax[100001];
vector<ppi> ans;

inline bool Intersect(const ppi &A, const ppi &B)
{
	pii iL = {max(A.fst.fst, B.fst.fst), max(A.fst.snd, B.fst.snd)};
	pii iR = {min(A.fst.fst + A.snd, B.fst.fst + B.snd), min(A.fst.snd + A.snd, B.fst.snd + B.snd)};

	return (iL.fst <= iR.fst && iL.snd <= iR.snd);
}

inline bool comp(const pii &L, const pii &R) {return make_pair(L.snd, L.fst) < make_pair(R.snd, R.fst);}
inline bool comp2(const ppi &L, const ppi &R) {return make_pair(L.snd, L.fst) > make_pair(R.snd, R.fst);}

vector<pii> use[3];
vector<ppi> tmp;

void brute(int d)
{
	if (d < N)
	{
		for (int i = 0; i < K; i++)
		{
			use[i].push_back(B[d]);
			brute(d + 1);
			use[i].pop_back();
		}
	}
	else if (d < N + K)
	{
		int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF;
		for (const auto &x : use[d - N]) 
		{
			mnY = min(mnY, x.snd); mxY = max(mxY, x.snd);
			mnX = min(mnX, x.fst); mxX = max(mxX, x.fst);
		}

		if (use[d - N].size() > 1)
		{
			if (mxY - mnY > mxX - mnX)
			{
				tmp.push_back({{mnX, mnY}, mxY - mnY});
				brute(d + 1);
				tmp.pop_back();
				tmp.push_back({{mxX - mxY + mnY, mnY}, mxY - mnY});
				brute(d + 1);
				tmp.pop_back();
			}
			else
			{
				tmp.push_back({{mnX, mnY}, mxX - mnX});
				brute(d + 1);
				tmp.pop_back();
				tmp.push_back({{mnX, mxY - mxX + mnX}, mxX - mnX});
				brute(d + 1);
				tmp.pop_back();
			}
		}
		else if (use[d - N].size() == 1)
		{
			tmp.push_back({{mnX, mnY}, 1});
			brute(d + 1);
			tmp.pop_back();
			tmp.push_back({{mnX - 1, mnY}, 1});
			brute(d + 1);
			tmp.pop_back();
			tmp.push_back({{mnX, mnY - 1}, 1});
			brute(d + 1);
			tmp.pop_back();
			tmp.push_back({{mnX - 1, mnY - 1}, 1});
			brute(d + 1);
			tmp.pop_back();
		}
		else
		{
			tmp.push_back({{-2000000000 - 2 * d, -2000000000 - 2 * d}, 1});
			brute(d + 1);
			tmp.pop_back();
		}	
	}
	else
	{
		bool valid = 1;
		for (int i = 0; i < tmp.size(); i++)
		{
			for (int j = i + 1; j < tmp.size(); j++) valid &= !Intersect(tmp[i], tmp[j]);
		}
		if (valid)
		{
			vector<ppi> tmp2 = tmp;
			sort(tmp2.begin(), tmp2.end(), comp2);
			if (ans.size() && ans[0].snd <= tmp2[0].snd) return;
			ans = tmp2;
		}
	}
}

inline void solve()
{
	if (A.size() < 2) return;
	for (int i = 0; i < A.size(); i++)
	{
		prefMin[i] = A[i]; prefMax[i] = A[i];
		if (i) 
		{
			prefMin[i].fst = min(prefMin[i - 1].fst, prefMin[i].fst);
			prefMin[i].snd = min(prefMin[i - 1].snd, prefMin[i].snd);
			prefMax[i].fst = max(prefMax[i - 1].fst, prefMax[i].fst);
			prefMax[i].snd = max(prefMax[i - 1].snd, prefMax[i].snd);
		}
	}
	for (int i = A.size() - 1; i >= 0; i--)
	{
		sufMin[i] = A[i]; sufMax[i] = A[i];
		if (i + 1 < N)
		{
			sufMin[i].fst = min(sufMin[i + 1].fst, sufMin[i].fst);
			sufMin[i].snd = min(sufMin[i + 1].snd, sufMin[i].snd);
			sufMax[i].fst = max(sufMax[i + 1].fst, sufMax[i].fst);
			sufMax[i].snd = max(sufMax[i + 1].snd, sufMax[i].snd);
		}
	}
	for (int i = 0; i + 1 < A.size(); i++)
	{
		pii aL = prefMin[i], aR = prefMax[i], bL = sufMin[i + 1], bR = sufMax[i + 1];
		int sA = max(aR.fst - aL.fst, aR.snd - aL.snd);
		int sB = max(bR.fst - bL.fst, bR.snd - bL.snd);

		if (sA == 0) {sA = 1;}
		if (sB == 0) {sB = 1;}

		aL.fst = aR.fst - sA; aL.snd = aR.snd - sA;

		if (Intersect({aL, sA}, {bL, sB})) continue;
		if (K == 3 && Intersect(sqr, {bL, sB})) continue;
		if (K == 3 && Intersect(sqr, {aL, sA})) continue;

		vector<ppi> temp;
		temp.push_back({aL, sA}); temp.push_back({bL, sB});
		if (K == 3) temp.push_back(sqr);

		sort(temp.begin(), temp.end(), comp2);

		if (ans.size() && ans[0].snd <= temp[0].snd) continue;
		ans = temp;
	}
}

int32_t main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF;
	for (int i = 0; i < N; i++) 
	{
		cin >> B[i].fst >> B[i].snd;
		mnY = min(mnY, B[i].snd); mxY = max(mxY, B[i].snd);
		mnX = min(mnX, B[i].fst); mxX = max(mxX, B[i].fst);
	}
	
	ans.push_back({{mnX, mnY}, max(1LL, max(mxX - mnX, mxY - mnY))});
	for (int j = 1; j < K; j++) ans.push_back({{-2000000000 - 2 * j, -2000000000 - 2 * j}, 1});

	if (K == 2)
	{
		for (int i = 0; i < N; i++) A.push_back(B[i]);
		sort(A.begin(), A.end()); solve();
		sort(A.begin(), A.end(), comp); solve();
	}
	else if (K == 3) {brute(0);}

	for (int i = 0; i < K; i++)
	{
		cout << ans[i].fst.fst << " " << ans[i].fst.snd << " " << ans[i].snd << "\n";
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

izvanzemaljci.cpp: In function 'void brute(long long int)':
izvanzemaljci.cpp:105:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for (int i = 0; i < tmp.size(); i++)
      |                   ~~^~~~~~~~~~~~
izvanzemaljci.cpp:107:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    for (int j = i + 1; j < tmp.size(); j++) valid &= !Intersect(tmp[i], tmp[j]);
      |                        ~~^~~~~~~~~~~~
izvanzemaljci.cpp: In function 'void solve()':
izvanzemaljci.cpp:122:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for (int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
izvanzemaljci.cpp:144:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for (int i = 0; i + 1 < A.size(); i++)
      |                  ~~~~~~^~~~~~~~~~

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