oj.uz

답안 #1002975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002975 2024-06-19T21:45:35 Z Lobo Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 57 ms 1688 KB 
#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 << (int) 2*1e9 << " " << (int) 2*1e9 << " " << 1 << endl;
		}
	}
}

Compilation message

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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 45 ms 1572 KB Output is correct
8 Correct 52 ms 1620 KB Output is correct
9 Correct 43 ms 1616 KB Output is correct
10 Correct 57 ms 1688 KB Output is correct
11 Correct 41 ms 848 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Expected integer, but "2e+09" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 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

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