oj.uz

Submission #1002979

# Submission time Handle Problem Language Result Execution time Memory
1002979 2024-06-19T21:49:55 Z Lalic Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 16 ms 3164 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

pair<int, pair<pii, pii>> getBest(int n, vector<pii> arr){
	int mxy=-INF, mny=INF;
	vector<int> esq(n-1);
	vector<pii> coord(n-1);
	for(int i=0;i<n-1;i++){
		mxy=max(mxy, arr[i].se); mny=min(mny, arr[i].se);
		esq[i]=max({arr[i].fi-arr[0].fi, mxy-mny, 1});
		coord[i]={arr[i].fi-esq[i], mny};
	}
	
	int best=INF;
	pii cor1={-1, -1}, cor2={-1, -1};
	
	mxy=-INF, mny=INF;
	for(int i=n-1;i>=1;i--){
		mxy=max(mxy, arr[i].se); mny=min(mny, arr[i].se);
		if(arr[i-1].fi!=arr[i].fi){
			int curr=max({arr[n-1].fi-arr[i].fi, mxy-mny, 1});
			if(max(curr, esq[i-1])<best){
				best=max(curr, esq[i-1]);
				cor1=coord[i-1];
				cor2={arr[i].fi, mny};
			}
		}
	}
	
	return {best, {cor1, cor2}};
}

void solve(){
	int n, k; cin >> n >> k;
	
	vector<pii> arr(n);
	for(auto& [a, b] : arr) cin >> a >> b;
	
	if(k==1){
		int mnx=INF, mxx=-INF, mny=INF, mxy=-INF;
		for(auto [a, b]: arr) mnx=min(mnx, a), mxx=max(mxx, a), mny=min(mny, b), mxy=max(mxy, b);
		cout << mnx << " " << mny << " " << max({mxx-mnx, mxy-mny, 1}) << "\n";
	}
	else if(k==2){
		sort(all(arr));
		pair<int, pair<pii, pii>> res = getBest(n, arr);
		for(int i=0;i<n;i++){
			int aux=arr[i].se;
			arr[i].se=arr[i].fi;
			arr[i].fi=aux;
		}
		sort(all(arr));
		pair<int, pair<pii, pii>> res1 = getBest(n, arr);
		swap(res1.se.fi.fi, res1.se.fi.se); swap(res1.se.se.fi, res1.se.se.se);
		if(res1.fi<res.fi) swap(res, res1);
		
		cout << res.se.fi.fi << " " << res.se.fi.se << " " << res.fi << "\n";
		cout << res.se.se.fi << " " << res.se.se.se << " " << res.fi << "\n";
	}
}
	

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int tt=1;
	//~ cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 3164 KB Output is correct
8 Correct 16 ms 3164 KB Output is correct
9 Correct 16 ms 3164 KB Output is correct
10 Correct 16 ms 3160 KB Output is correct
11 Correct 16 ms 1656 KB Output is correct

Subtask #2
0 / 21.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -