oj.uz

답안 #420776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420776 2021-06-08T13:51:38 Z Berted Izvanzemaljci (COI21_izvanzemaljci) C++14
5 / 100
 61 ms 8004 KB 
#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#define int long long
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second

using namespace std;

const int INF = 1e9 + 7;

int N, K;
pii A[100001];

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

inline bool comp(const pii &L, const pii &R) {return make_pair(L.snd, L.fst) < make_pair(R.snd, R.fst);}
inline void solve()
{
	for (int i = 0; i < N; 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 = N - 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 < N; 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; aL.fst--; aL.snd--;}
		if (sB == 0) {sB = 1;}

		pii iL = {max(aL.fst, bL.fst), max(aL.snd, bL.snd)};
		pii iR = {min(aL.fst + sA, bL.fst + sB), min(aL.snd + sA, bL.snd + sB)};

		if (iL.fst <= iR.fst && iL.snd <= iR.snd) continue;

		if (sA > sB)
		{
			if (ans.size() && ans[0].snd <= sA) continue;
			ans.clear();
			ans.push_back({aL, sA}); ans.push_back({bL, sB});
		}
		else
		{
			if (ans.size() && ans[0].snd <= sB) continue;
			ans.clear();
			ans.push_back({bL, sB}); ans.push_back({aL, sA});
		}

	}
}

int32_t main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	if (K == 1)
	{
		int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF;
		for (int i = 0; i < N; i++)
		{
			int x, y; cin >> x >> y;
			mnY = min(mnY, y); mxY = max(mxY, y);
			mnX = min(mnX, x); mxX = max(mxX, x);
		}
		cout << mnX << " " << mnY << " " << max(1LL, max(mxX - mnX, mxY - mnY)) << "\n";
	}
	else if (K == 2)
	{
		int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF;
		for (int i = 0; i < N; i++) 
		{
			cin >> A[i].fst >> A[i].snd;
			mnY = min(mnY, A[i].snd); mxY = max(mxY, A[i].snd);
			mnX = min(mnX, A[i].fst); mxX = max(mxX, A[i].fst);
		}
		
		ans.push_back({{mnX, mnY}, max(1LL, max(mxX - mnX, mxY - mnY))});
		ans.push_back({{-2000000000, -2000000000}, 1});

		sort(A, A + N); solve();
		sort(A, A + N, comp); solve();

		//if (ans.size() < K) return 0;

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 26 ms 204 KB Output is correct
8 Correct 27 ms 304 KB Output is correct
9 Correct 34 ms 300 KB Output is correct
10 Correct 34 ms 204 KB Output is correct
11 Correct 27 ms 204 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 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 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Incorrect 61 ms 8004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -