Submission #1002973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002973		Lobo	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	47 ms	408 KiB

izvanzemaljci

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e18+10;

pair<pair<int,int>,int> sqr(int x0, int x1, int y0, int y1) {
	int l = max({(int) 1,x1-x0,y1-y0});
	return mp(mp(x0,y0),l);
}

int32_t main() {
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif

	int n,k;
	cin >> n >> k;

	if(k == 1) {	
		int minx = inf,miny=inf,maxx = -inf,maxy = -inf;
		for(int i = 0; i < n; i++) {
			int x,y;
			cin >> x >> y;
			minx = min(x,minx);
			maxx = max(x,maxx);
			miny = min(y,miny);
			maxy = max(y,maxy);
		}
		auto a = sqr(minx,maxx,miny,maxy);
		cout << a.fr.fr << " " << a.fr.sc << " " << a.sc << endl;
	}
	else if(k == 2) {
		vector<pair<pair<int,int>,int>> ansv;
		int ans = inf;

		vector<pair<int,int>> pts;
		for(int i = 0; i < n; i++) {
			int x,y;
			cin >> x >> y;
			pts.pb(mp(x,y));
		}

		{
			sort(all(pts));
			vector<pair<pair<int,int>,int>> pfsq(n+10);
			int minx = inf,miny=inf,maxx = -inf,maxy = -inf;
			for(int i = 0; i < n; i++) {
				int x = pts[i].fr;
				int y = pts[i].sc;

				minx = min(x,minx);
				maxx = max(x,maxx);
				miny = min(y,miny);
				maxy = max(y,maxy);
				pfsq[i] = sqr(minx,maxx,miny,maxy);
			}

			vector<pair<pair<int,int>,int>> sfsq(n+10);
			minx = inf,miny=inf,maxx = -inf,maxy = -inf;
			for(int i = n-1; i >= 0; i--) {
				int x = pts[i].fr;
				int y = pts[i].sc;

				minx = min(x,minx);
				maxx = max(x,maxx);
				miny = min(y,miny);
				maxy = max(y,maxy);
				sfsq[i] = sqr(minx,maxx,miny,maxy);
			}

			for(int i = 0; i+1 < n; i++) {
				int x0 = pfsq[i].fr.fr;
				int y0 = pfsq[i].fr.sc;
				int l0 = pfsq[i].sc;
				int x1 = sfsq[i+1].fr.fr;
				int y1 = sfsq[i+1].fr.sc;
				int l1 = sfsq[i+1].sc;
				
				bool inter = true;
				if(x1 > x0+l0 or x0 > x1+l1) inter = false;
				if(x1 > x0+l0 or y0 > y1+l1) inter = false;
				if(inter == true) continue;
				if(max(l0,l1) > ans) continue;
				ansv.clear();
				ansv.pb(mp(mp(x0,y0),l0));
				ansv.pb(mp(mp(x1,y1),l1));
				ans = max(l0,l1);
			}

			for(int i = 0; i < pts.size(); i++) {
				swap(pts[i].fr,pts[i].sc);
			}
		}

		{
			sort(all(pts));
			vector<pair<pair<int,int>,int>> pfsq(n+10);
			int minx = inf,miny=inf,maxx = -inf,maxy = -inf;
			for(int i = 0; i < n; i++) {
				int x = pts[i].sc;
				int y = pts[i].fr;
				minx = min(x,minx);
				maxx = max(x,maxx);
				miny = min(y,miny);
				maxy = max(y,maxy);
				pfsq[i] = sqr(minx,maxx,miny,maxy);
			}

			vector<pair<pair<int,int>,int>> sfsq(n+10);
			minx = inf,miny=inf,maxx = -inf,maxy = -inf;
			for(int i = n-1; i >= 0; i--) {
				int x = pts[i].sc;
				int y = pts[i].fr;

				minx = min(x,minx);
				maxx = max(x,maxx);
				miny = min(y,miny);
				maxy = max(y,maxy);
				sfsq[i] = sqr(minx,maxx,miny,maxy);
			}

			for(int i = 0; i+1 < n; i++) {
				int x0 = pfsq[i].fr.fr;
				int y0 = pfsq[i].fr.sc;
				int l0 = pfsq[i].sc;
				int x1 = sfsq[i+1].fr.fr;
				int y1 = sfsq[i+1].fr.sc;
				int l1 = sfsq[i+1].sc;
				
				bool inter = true;
				if(x1 > x0+l0 or x0 > x1+l1) inter = false;
				if(y1 > y0+l0 or y0 > y1+l1) inter = false;
				if(inter == true) continue;
				if(max(l0,l1) > ans) continue;
				ansv.clear();
				ansv.pb(mp(mp(x0,y0),l0));
				ansv.pb(mp(mp(x1,y1),l1));
				ans = max(l0,l1);
			}

			for(int i = 0; i < pts.size(); i++) {
				swap(pts[i].fr,pts[i].sc);
			}
		}

		if(ans != inf) {
			for(auto x : ansv) {
				cout << x.fr.fr << " " << x.fr.sc << " " << x.sc << endl;
			}
		}
		else {
			int minx = inf,miny=inf,maxx = -inf,maxy = -inf;
			for(int i = 0; i < n; i++) {
				int x,y;
				cin >> x >> y;
				minx = min(x,minx);
				maxx = max(x,maxx);
				miny = min(y,miny);
				maxy = max(y,maxy);
			}
			auto a = sqr(minx,maxx,miny,maxy);
			cout << a.fr.fr << " " << a.fr.sc << " " << a.sc << endl;
			cout << 2*1e9 << " " << 2*1e9 << " " << 1 << endl;
		}
	}
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int32_t main()':
izvanzemaljci.cpp:96:21: 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]
   96 |    for(int i = 0; i < pts.size(); i++) {
      |                   ~~^~~~~~~~~~~~
izvanzemaljci.cpp:147:21: 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]
  147 |    for(int i = 0; i < pts.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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