oj.uz

Submission #421162

# Submission time Handle Problem Language Result Execution time Memory
421162 2021-06-08T19:37:08 Z Nicholas_Patrick Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 62 ms 2600 KB 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct point{
	int x, y;
};
struct compx{
	bool operator()(point a, point b)const{
		return a.x<b.x;
	}
};
int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	vector<point> points(n);
	for(auto& i : points)
		scanf("%d%d", &i.x, &i.y);
	int minx=1e9, maxx=-1e9, miny=1e9, maxy=-1e9;
	for(auto i : points){
		minx=min(minx, i.x);
		maxx=max(maxx, i.x);
		miny=min(miny, i.y);
		maxy=max(maxy, i.y);
	}
	int l=max({maxx-minx, maxy-miny, 1});
	if(k==1){
		printf("%d %d %d\n", minx, miny, l);
	}else if(k==2){
		int best=l, x1=minx, y1=miny, s1=l, x2=2.1e9, y2=2.1e9, s2=1;
		{
			sort(points.begin(), points.end(), [&](point a, point b){
				return a.x<b.x;
			});
			vector<int> pmax(n+1), smax(n+1), pmin(n+1), smin(n+1);
			pmax[0]=-1e9, pmin[0]=1e9;
			for(int i=0; i<n; i++){
				pmax[i+1]=max(pmax[i], points[i].y);
				pmin[i+1]=min(pmin[i], points[i].y);
			}
			smax[n]=-1e9, smin[n]=1e9;
			for(int i=n; i--;){
				smax[i]=max(smax[i+1], points[i].y);
				smin[i]=min(smin[i+1], points[i].y);
			}
			for(int i=1; i<n; i++){
				if(points[i-1].x<points[i].x){
					int cx1, cy1, cs1, cx2, cy2, cs2;
					cx1=points[i-1].x;
					cy1=pmin[i];
					cs1=max({points[i-1].x-points[0].x, pmax[i]-pmin[i], 1});
					cx1-=cs1;
					cx2=points[i].x;
					cy2=smin[i];
					cs2=max({points[n-1].x-points[i].x, smax[i]-smin[i], 1});
					if(max(cs1, cs2)<best){
						best=max(cs1, cs2);
						x1=cx1;
						y1=cy1;
						s1=cs1;
						x2=cx2;
						y2=cy2;
						s2=cs2;
					}
				}
			}
		}
		{
			sort(points.begin(), points.end(), [&](point a, point b){
				return a.y<b.y;
			});
			vector<int> pmax(n+1), smax(n+1), pmin(n+1), smin(n+1);
			pmax[0]=-1e9, pmin[0]=1e9;
			for(int i=0; i<n; i++){
				pmax[i+1]=max(pmax[i], points[i].x);
				pmin[i+1]=min(pmin[i], points[i].x);
			}
			smax[n]=-1e9, smin[n]=1e9;
			for(int i=n; i--;){
				smax[i]=max(smax[i+1], points[i].x);
				smin[i]=min(smin[i+1], points[i].x);
			}
			for(int i=1; i<n; i++){
				if(points[i-1].y<points[i].y){
					int cy1, cx1, cs1, cy2, cx2, cs2;
					cx1=pmin[i];
					cy1=points[i-1].y;
					cs1=max({points[i-1].y-points[0].y, pmax[i]-pmin[i], 1});
					cy1-=cs1;
					cx2=smin[i];
					cy2=points[i].y;
					cs2=max({points[n-1].y-points[i].y, smax[i]-smin[i], 1});
					if(max(cs1, cs2)<best){
						best=max(cs1, cs2);
						x1=cx1;
						y1=cy1;
						s1=cs1;
						x2=cx2;
						y2=cy2;
						s2=cs2;
					}
				}
			}
		}
		printf("%d %d %d\n%d %d %d\n", x1, y1, s1, x2, y2, s2);
	}
}

Compilation message

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d%d", &i.x, &i.y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 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 29 ms 972 KB Output is correct
8 Correct 31 ms 972 KB Output is correct
9 Correct 29 ms 972 KB Output is correct
10 Correct 29 ms 1056 KB Output is correct
11 Correct 30 ms 972 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 324 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 62 ms 2600 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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