oj.uz

Submission #420883

# Submission time Handle Problem Language Result Execution time Memory
420883 2021-06-08T14:37:39 Z Berted Izvanzemaljci (COI21_izvanzemaljci) C++14
38 / 100
 3000 ms 9796 KB 
#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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 28 ms 1792 KB Output is correct
8 Correct 28 ms 1772 KB Output is correct
9 Correct 27 ms 1860 KB Output is correct
10 Correct 27 ms 1860 KB Output is correct
11 Correct 28 ms 1868 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 75 ms 9764 KB Output is correct
11 Correct 72 ms 9784 KB Output is correct
12 Correct 74 ms 9768 KB Output is correct
13 Correct 75 ms 9788 KB Output is correct
14 Correct 72 ms 9796 KB Output is correct
15 Correct 73 ms 9788 KB Output is correct
16 Correct 72 ms 9732 KB Output is correct
17 Correct 69 ms 8996 KB Output is correct
18 Correct 67 ms 8748 KB Output is correct
19 Correct 60 ms 7996 KB Output is correct
20 Correct 62 ms 8508 KB Output is correct
21 Correct 77 ms 9704 KB Output is correct
22 Correct 109 ms 9736 KB Output is correct
23 Correct 73 ms 9752 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 30 ms 324 KB Output is correct
16 Correct 25 ms 332 KB Output is correct
17 Correct 72 ms 312 KB Output is correct
18 Correct 71 ms 204 KB Output is correct
19 Correct 206 ms 204 KB Output is correct
20 Correct 210 ms 316 KB Output is correct
21 Correct 209 ms 308 KB Output is correct
22 Correct 246 ms 312 KB Output is correct
23 Correct 233 ms 308 KB Output is correct
24 Correct 208 ms 320 KB Output is correct
25 Correct 213 ms 308 KB Output is correct
26 Correct 217 ms 204 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -