oj.uz

Submission #744145

# Submission time Handle Problem Language Result Execution time Memory
744145 2023-05-18T08:34:32 Z jamielim Izvanzemaljci (COI21_izvanzemaljci) C++14
5 / 100
 3000 ms 47256 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,k;
vector<ii> all;
map<int,vector<int> > m[2];
vector<int> disc[2];
map<int,int> rev[2];
int sufmin[2][100005];
int premin[2][100005];
int sufmax[2][100005];
int premax[2][100005];

vector<int> find_one_square(vector<ii> v){
	if(SZ(v)==0)return {0,0,1};
	int minx=LLINF,maxx=-LLINF,miny=LLINF,maxy=-LLINF;
	for(ii i:v){
		minx=min(minx,i.fi);
		maxx=max(maxx,i.fi);
		miny=min(miny,i.se);
		maxy=max(maxy,i.se);
	}
	int l=max(1LL,max(maxx-minx,maxy-miny));
	return {minx,miny,l};
}

bool disjoint(vector<int> v1,vector<int> v2){
	return (v1[0]+v1[2]<v2[0])||(v2[0]+v2[2]<v1[0])||(v1[1]+v1[2]<v2[1])||(v2[1]+v2[2]<v1[1]);
}

int32_t main(){
	scanf("%lld%lld",&n,&k);
	int x,y;
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&x,&y);
		all.pb(x,y);
		m[0][x].pb(y);
		m[1][y].pb(x);
	}
	for(int i=0;i<2;i++){
		for(auto it=m[i].begin();it!=m[i].end();++it)disc[i].pb(it->fi);
		sort(ALL(disc[i]));
		disc[i].resize(unique(ALL(disc[i]))-disc[i].begin());
		for(int j=0;j<SZ(disc[i]);j++)rev[i][disc[i][j]]=j+1;
		for(auto it=m[i].begin();it!=m[i].end();++it)sort(ALL(it->se));
		premin[i][0]=LLINF;premax[i][0]=-LLINF;
		sufmin[i][SZ(disc[i])+1]=LLINF;sufmax[i][SZ(disc[i])+1]=-LLINF;
		int ctr=1;
		for(auto it=m[i].begin();it!=m[i].end();++it,ctr++){
			premin[i][ctr]=min(premin[i][ctr-1],it->se.front());
			premax[i][ctr]=max(premax[i][ctr-1],it->se.back());
		}
		ctr=SZ(disc[i]);
		for(auto it=m[i].rbegin();it!=m[i].rend();++it,ctr--){
			sufmin[i][ctr]=min(sufmin[i][ctr+1],it->se.front());
			sufmax[i][ctr]=max(sufmax[i][ctr+1],it->se.back());
		}
		//for(int j=0;j<=SZ(disc[i])+1;j++)printf("%d %d %d %d\n",premin[i][j],premax[i][j],sufmin[i][j],sufmax[i][j]);
	}
	if(k==1){
		vector<int> ans=find_one_square(all);
		printf("%lld %lld %lld\n",ans[0],ans[1],ans[2]);
	}else if(k==2){
		int le=1,ri=find_one_square(all)[2];
		vector<int> ans[2];
		while(le<ri){
			int mi=(le+ri)/2;
			bool poss=0;
			for(int i=0;i<n;i++){
				//printf("bsta %d\n",i);
				x=all[i].fi;y=all[i].se;
				if(sufmin[0][rev[0][x]+1]>y||sufmin[1][rev[1][y]+1]>x){
					if(x-le<=premin[1][rev[1][y]]&&y-le<=premin[0][rev[0][x]]){ // bottom left stuff are within range
						if(sufmin[0][rev[0][x]+1]>y){
							if(rev[1][y]<SZ(disc[1])){
								int hor=sufmax[1][rev[1][y]+1]-sufmin[1][rev[1][y]+1];
								int ver=premax[0][SZ(disc[0])]-disc[1][rev[1][y]+1-1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(rev[0][x]<SZ(disc[0])){
								int hor=premax[1][SZ(disc[1])]-disc[0][rev[0][x]+1-1];
								int ver=sufmax[0][rev[0][x]+1]-sufmin[0][rev[0][x]+1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}
					}
				}
				if(sufmax[0][rev[0][x]+1]<y||premin[1][rev[1][y]-1]>x){
					if(x-le<=sufmin[1][rev[1][y]]&&y+le>=premax[0][rev[0][x]]){ // top left stuff are within range
						if(sufmax[0][rev[0][x]+1]<y){
							if(rev[1][y]>1){
								int hor=premax[1][rev[1][y]-1]-premin[1][rev[1][y]-1];
								int ver=disc[1][rev[1][y]-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(rev[0][x]<SZ(disc[0])){
								int hor=premax[1][SZ(disc[1])]-disc[0][rev[0][x]+1-1];
								int ver=sufmax[0][rev[0][x]+1]-sufmin[0][rev[0][x]+1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}
					}
				}
				if(premax[0][rev[0][x]-1]<y||premax[1][rev[1][y]-1]<x){
					if(x+le>=sufmax[1][rev[1][y]]&&y+le>=sufmax[0][rev[0][x]]){ // top right stuff are within range
						if(premax[0][rev[0][x]-1]<y){
							if(rev[1][y]>1){
								int hor=premax[1][rev[1][y]-1]-premin[1][rev[1][y]-1];
								int ver=disc[1][rev[1][y]-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(rev[0][x]>1){
								int hor=disc[0][rev[0][x]-1-1]-premin[1][SZ(disc[1])];
								int ver=premax[1][rev[0][x]-1]-premin[1][rev[0][x]-1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}
					}
				}
				if(premin[0][rev[0][x]-1]>y||sufmax[1][rev[1][y]+1]<x){
					if(x+le>=premax[1][rev[1][y]]&&y-le<=sufmin[0][rev[0][x]]){ // bottom right stuff are within range
						if(premin[0][rev[0][x]-1]>y){
							if(rev[1][y]<SZ(disc[1])){
								int hor=sufmax[1][rev[1][y]+1]-sufmin[1][rev[1][y]+1];
								int ver=premax[0][SZ(disc[0])]-disc[1][rev[1][y]+1-1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(rev[0][x]>1){
								int hor=disc[0][rev[0][x]-1-1]-premin[1][SZ(disc[1])];
								int ver=premax[1][rev[0][x]-1]-premin[1][rev[0][x]-1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}
					}
				}
			}
			if(poss)ri=mi;
			else le=mi+1;
		}
		//printf("%lld\n",le);
		/*reconstruct*/
			for(int i=0;i<n;i++){
				//printf("%d\n",i);
				x=all[i].fi;y=all[i].se;
				if(sufmin[0][rev[0][x]+1]>y||sufmin[1][rev[1][y]+1]>x){
					if(x-le<=premin[1][rev[1][y]]&&y-le<=premin[0][rev[0][x]]){ // bottom left stuff are within range
						if(sufmin[0][rev[0][x]+1]>y){
							if(rev[1][y]<SZ(disc[1])){
								int hor=sufmax[1][rev[1][y]+1]-sufmin[1][rev[1][y]+1];
								int ver=premax[0][SZ(disc[0])]-disc[1][rev[1][y]+1-1];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y-le,le};
									ans[1]={sufmin[1][rev[1][y]+1],disc[1][rev[1][y]+1-1],le};
									break;
								}
							}else{
								ans[0]={x-le,y-le,le};
								ans[1]={x-le-2,y-le-2,1};
								break;
							}
						}else{
							if(rev[0][x]<SZ(disc[0])){
								int hor=premax[1][SZ(disc[1])]-disc[0][rev[0][x]+1-1];
								int ver=sufmax[0][rev[0][x]+1]-sufmin[0][rev[0][x]+1];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y-le,le};
									ans[1]={disc[0][rev[0][x]+1-1],sufmin[0][rev[0][x]+1],le};
									break;
								}
							}else{
								ans[0]={x-le,y-le,le};
								ans[1]={x-le-2,y-le-2,1};
								break;
							}
						}
					}
				}
				if(sufmax[0][rev[0][x]+1]<y||premin[1][rev[1][y]-1]>x){
					if(x-le<=sufmin[1][rev[1][y]]&&y+le>=premax[0][rev[0][x]]){ // top left stuff are within range
						if(sufmax[0][rev[0][x]+1]<y){
							if(rev[1][y]>1){
								int hor=premax[1][rev[1][y]-1]-premin[1][rev[1][y]-1];
								int ver=disc[1][rev[1][y]-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y,le};
									ans[1]={premin[1][rev[1][y]-1],disc[1][rev[1][y]-1-1]-le,le};
									break;
								}
							}else{
								ans[0]={x-le,y,le};
								ans[1]={x-le-2,y-2,1};
								break;
							}
						}else{
							if(rev[0][x]<SZ(disc[0])){
								int hor=premax[1][SZ(disc[1])]-disc[0][rev[0][x]+1-1];
								int ver=sufmax[0][rev[0][x]+1]-sufmin[0][rev[0][x]+1];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y,le};
									ans[1]={disc[0][rev[0][x]+1-1],sufmax[0][rev[0][x]+1]-le,le};
									break;
								}
							}else{
								ans[0]={x-le,y,le};
								ans[1]={x-le-2,y-2,1};
								break;
							}
						}
					}
				}
				if(premax[0][rev[0][x]-1]<y||premax[1][rev[1][y]-1]<x){
					if(x+le>=sufmax[1][rev[1][y]]&&y+le>=sufmax[0][rev[0][x]]){ // top right stuff are within range
						if(premax[0][rev[0][x]-1]<y){
							if(rev[1][y]>1){
								int hor=premax[1][rev[1][y]-1]-premin[1][rev[1][y]-1];
								int ver=disc[1][rev[1][y]-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=le){
									ans[0]={x,y,le};
									ans[1]={premax[1][rev[1][y]-1]-le,disc[1][rev[1][y]-1-1]-le,le};
									break;
								}
							}else{
								ans[0]={x,y,le};
								ans[1]={x-2,y-2,1};
								break;
							}
						}else{
							if(rev[0][x]>1){
								int hor=disc[0][rev[0][x]-1-1]-premin[1][SZ(disc[1])];
								int ver=premax[1][rev[0][x]-1]-premin[1][rev[0][x]-1];
								if(max(hor,ver)<=le){
									ans[0]={x,y,le};
									ans[1]={disc[0][rev[0][x]-1-1]-le,premax[1][rev[0][x]-1]-le,le};
									break;
								}
							}else{
								ans[0]={x,y,le};
								ans[1]={x-2,y-2,1};
								break;
							}
						}
					}
				}
				if(premin[0][rev[0][x]-1]>y||sufmax[1][rev[1][y]+1]<x){
					if(x+le>=premax[1][rev[1][y]]&&y-le<=sufmin[0][rev[0][x]]){ // bottom right stuff are within range
						if(premin[0][rev[0][x]-1]>y){
							if(rev[1][y]<SZ(disc[1])){
								int hor=sufmax[1][rev[1][y]+1]-sufmin[1][rev[1][y]+1];
								int ver=premax[0][SZ(disc[0])]-disc[1][rev[1][y]+1-1];
								if(max(hor,ver)<=le){
									ans[0]={x,y-le,le};
									ans[1]={sufmax[1][rev[1][y]+1]-le,disc[1][rev[1][y]+1-1],le};
									break;
								}
							}else{
								ans[0]={x,y-le,le};
								ans[1]={x-2,y-le-2,1};
								break;
							}
						}else{
							if(rev[0][x]>1){
								int hor=disc[0][rev[0][x]-1-1]-premin[1][SZ(disc[1])];
								int ver=premax[1][rev[0][x]-1]-premin[1][rev[0][x]-1];
								if(max(hor,ver)<=le){
									ans[0]={x,y-le,le};
									ans[1]={disc[0][rev[0][x]-1-1]-le,premin[1][rev[0][x]-1],le};
									break;
								}
							}else{
								ans[0]={x,y-le,le};
								ans[1]={x-2,y-le-2,1};
								break;
							}
						}
					}
				}
			}
		/*end of reconstruct*/
		for(int i=0;i<2;i++){for(int j=0;j<3;j++)printf("%lld ",ans[i][j]);printf("\n");}
	}else{
		
	}
}
/*
5 2
1 3
3 1
5 5
5 10
7 7
*/

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 319 ms 45684 KB Output is correct
8 Correct 333 ms 45644 KB Output is correct
9 Correct 324 ms 45616 KB Output is correct
10 Correct 310 ms 45680 KB Output is correct
11 Correct 378 ms 45668 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Execution timed out 3060 ms 47256 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 2 ms 724 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 2 ms 724 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -