Submission #744254

#	Time	Username	Problem	Language	Result	Execution time	Memory
744254		kxd	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	27 ms	1876 KiB

izvanzemaljci

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<int,int>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define forn(i, n) for (int i = 0; i < n; i++)
#define forn1(i, n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second

using namespace std;
const int N = 1e5+5;
const int inf = 1e9;
const int INF = 1e18;
const int MOD = 1e9+7;

pii a[N];
int MINX[N], MINY[N], MAXX[N], MAXY[N];
int minx = INF, miny = INF, maxx = -INF, maxy = -INF;
int minx2 = INF, miny2 = INF, maxx2 = -INF, maxy2 = -INF;
int n, k;

int findL(int maxx, int maxy, int minx, int miny) {
	return max(1ll,max(maxx-minx,maxy-miny));
}


bool cmp(pii i, pii j) {
	return findL(i.ft,i.sd,minx,miny) < findL(j.ft,j.sd,minx,miny);
}


signed main() {
	INIT
	cin >> n >> k;
	int x, y;
	forn(i,n) {
		cin >> x >> y;
		minx = min(x,minx);
		miny = min(y,miny);
		maxx = max(x,maxx);
		maxy = max(y,maxy);
		a[i].ft = x, a[i].sd = y;
	}
	if(k==1) {
		cout << minx << ' ' << miny << ' ' << findL(maxx,maxy,minx,miny);
		return 0;
	}
	if(n==1) {
		cout << minx << ' ' << miny << ' ' << findL(maxx,maxy,minx,miny);
		cout << "0 0 1" << endl;
	}
	sort(a,a+n,cmp);
	int ansL = INF;
	int ansi = -1;
	vector<int> v;
	for (int j = n-1; j > 0; j--) {
		x = a[j].ft, y = a[j].sd;
		minx2 = min(x,minx2);
		miny2 = min(y,miny2);
		maxx2 = max(x,maxx2);
		maxy2 = max(y,maxy2);
		int l = max(findL(a[j-1].ft,a[j-1].sd,minx,miny), findL(maxx2,maxy2,minx2,miny2));
		//cout << j << ' ' << l << '|' << '(' << a[j-1].ft << ',' << a[j-1].sd << ')' << "||" << '(' << x << ',' << y << ')' << '|' << maxx2 << maxy2 << minx2 << miny2 << endl;
		if(l<ansL) {
			//cout << '*' << endl;
			ansi = j;
			ansL = l;
			v = {maxx2,maxy2,minx2,miny2};
		}
	}
	cout << minx << ' ' << miny << ' ' << findL(a[ansi-1].ft,a[ansi-1].sd,minx,miny) << endl;
	cout << v[2] << ' ' << v[3] << ' ' << findL(v[0],v[1],v[2],v[3]) << endl;
}

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