oj.uz

Submission #420844

# Submission time Handle Problem Language Result Execution time Memory
420844 2021-06-08T14:21:11 Z Berted Izvanzemaljci (COI21_izvanzemaljci) C++14
26 / 100
 85 ms 9788 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);}

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)
	{

	}

	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 solve()':
izvanzemaljci.cpp:39: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]
   39 |  for (int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
izvanzemaljci.cpp:61: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]
   61 |  for (int i = 0; i + 1 < A.size(); i++)
      |                  ~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 204 KB Output is correct
7 Correct 36 ms 1880 KB Output is correct
8 Correct 30 ms 1836 KB Output is correct
9 Correct 27 ms 1860 KB Output is correct
10 Correct 28 ms 1776 KB Output is correct
11 Correct 28 ms 1748 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 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 73 ms 9736 KB Output is correct
11 Correct 78 ms 9784 KB Output is correct
12 Correct 74 ms 9724 KB Output is correct
13 Correct 76 ms 9740 KB Output is correct
14 Correct 80 ms 9732 KB Output is correct
15 Correct 75 ms 9788 KB Output is correct
16 Correct 76 ms 9724 KB Output is correct
17 Correct 85 ms 9052 KB Output is correct
18 Correct 70 ms 8764 KB Output is correct
19 Correct 59 ms 7968 KB Output is correct
20 Correct 64 ms 8440 KB Output is correct
21 Correct 74 ms 9724 KB Output is correct
22 Correct 73 ms 9732 KB Output is correct
23 Correct 74 ms 9744 KB Output is correct

Subtask #3
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 1 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 384 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -