Submission #744155

#	Time	Username	Problem	Language	Result	Execution time	Memory
744155		jamielim	Izvanzemaljci (COI21_izvanzemaljci)	C++14	5 / 100	2296 ms	73520 KiB

izvanzemaljci

#include <bits/stdc++.h>
using namespace std;

#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<ll> find_one_square(vector<ii> v){
	if(SZ(v)==0)return {0,0,1};
	ll minx=LLINF,maxx=-LLINF,miny=LLINF,maxy=-LLINF;
	for(ii i:v){
		minx=min(minx,(ll)i.fi);
		maxx=max(maxx,(ll)i.fi);
		miny=min(miny,(ll)i.se);
		maxy=max(maxy,(ll)i.se);
	}
	ll 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("%d%d",&n,&k);
	int x,y;
	for(int i=0;i<n;i++){
		scanf("%d%d",&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]=2*INF;premax[i][0]=-2*INF;
		sufmin[i][SZ(disc[i])+1]=2*INF;sufmax[i][SZ(disc[i])+1]=-2*INF;
		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<ll> ans=find_one_square(all);
		printf("%lld %lld %lld\n",ans[0],ans[1],ans[2]);
	}else if(k==2){
		ll le=1,ri=find_one_square(all)[2];
		vector<ll> ans[2];
		while(le<ri){
			ll 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;
				int X=rev[0][x],Y=rev[1][y];
				if(sufmin[0][X+1]>y||sufmin[1][Y+1]>x){
					if(x-le<=premin[1][Y]&&y-le<=premin[0][X]){ // bottom left stuff are within range
						if(sufmin[0][X+1]>y){
							if(Y<SZ(disc[1])){
								ll hor=sufmax[1][Y+1]-sufmin[1][Y+1];
								ll ver=premax[0][SZ(disc[0])]-disc[1][Y+1-1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(X<SZ(disc[0])){
								ll hor=premax[1][SZ(disc[1])]-disc[0][X+1-1];
								ll ver=sufmax[0][X+1]-sufmin[0][X+1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}
					}
				}
				if(sufmax[0][X+1]<y||premin[1][Y-1]>x){
					if(x-le<=sufmin[1][Y]&&y+le>=premax[0][X]){ // top left stuff are within range
						if(sufmax[0][X+1]<y){
							if(Y>1){
								ll hor=premax[1][Y-1]-premin[1][Y-1];
								ll ver=disc[1][Y-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(X<SZ(disc[0])){
								ll hor=premax[1][SZ(disc[1])]-disc[0][X+1-1];
								ll ver=sufmax[0][X+1]-sufmin[0][X+1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}
					}
				}
				if(premax[0][X-1]<y||premax[1][Y-1]<x){
					if(x+le>=sufmax[1][Y]&&y+le>=sufmax[0][X]){ // top right stuff are within range
						if(premax[0][X-1]<y){
							if(Y>1){
								ll hor=premax[1][Y-1]-premin[1][Y-1];
								ll ver=disc[1][Y-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(X>1){
								ll hor=disc[0][X-1-1]-premin[1][SZ(disc[1])];
								ll ver=premax[1][X-1]-premin[1][X-1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}
					}
				}
				if(premin[0][X-1]>y||sufmax[1][X+1]<x){
					if(x+le>=premax[1][X]&&y-le<=sufmin[0][X]){ // bottom right stuff are within range
						if(premin[0][X-1]>y){
							if(Y<SZ(disc[1])){
								ll hor=sufmax[1][Y+1]-sufmin[1][Y+1];
								ll ver=premax[0][SZ(disc[0])]-disc[1][Y+1-1];
								if(max(hor,ver)<=mi){poss=1;break;}
							}else{
								poss=1;break;
							}
						}else{
							if(X>1){
								ll hor=disc[0][X-1-1]-premin[1][SZ(disc[1])];
								ll ver=premax[1][X-1]-premin[1][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;
				int X=rev[0][x],Y=rev[1][y];
				if(sufmin[0][X+1]>y||sufmin[1][Y+1]>x){
					if(x-le<=premin[1][Y]&&y-le<=premin[0][X]){ // bottom left stuff are within range
						if(sufmin[0][X+1]>y){
							if(Y<SZ(disc[1])){
								ll hor=sufmax[1][Y+1]-sufmin[1][Y+1];
								ll ver=premax[0][SZ(disc[0])]-disc[1][Y+1-1];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y-le,le};
									ans[1]={sufmin[1][Y+1],disc[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(X<SZ(disc[0])){
								ll hor=premax[1][SZ(disc[1])]-disc[0][X+1-1];
								ll ver=sufmax[0][X+1]-sufmin[0][X+1];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y-le,le};
									ans[1]={disc[0][X+1-1],sufmin[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][X+1]<y||premin[1][Y-1]>x){
					if(x-le<=sufmin[1][Y]&&y+le>=premax[0][X]){ // top left stuff are within range
						if(sufmax[0][X+1]<y){
							if(Y>1){
								ll hor=premax[1][Y-1]-premin[1][Y-1];
								ll ver=disc[1][Y-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y,le};
									ans[1]={premin[1][Y-1],disc[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(X<SZ(disc[0])){
								ll hor=premax[1][SZ(disc[1])]-disc[0][X+1-1];
								ll ver=sufmax[0][X+1]-sufmin[0][X+1];
								if(max(hor,ver)<=le){
									ans[0]={x-le,y,le};
									ans[1]={disc[0][X+1-1],sufmax[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][X-1]<y||premax[1][Y-1]<x){
					if(x+le>=sufmax[1][Y]&&y+le>=sufmax[0][X]){ // top right stuff are within range
						if(premax[0][X-1]<y){
							if(Y>1){
								ll hor=premax[1][Y-1]-premin[1][Y-1];
								ll ver=disc[1][Y-1-1]-premin[0][SZ(disc[0])];
								if(max(hor,ver)<=le){
									ans[0]={x,y,le};
									ans[1]={premax[1][Y-1]-le,disc[1][Y-1-1]-le,le};
									break;
								}
							}else{
								ans[0]={x,y,le};
								ans[1]={x-2,y-2,1};
								break;
							}
						}else{
							if(X>1){
								ll hor=disc[0][X-1-1]-premin[1][SZ(disc[1])];
								ll ver=premax[1][X-1]-premin[1][X-1];
								if(max(hor,ver)<=le){
									ans[0]={x,y,le};
									ans[1]={disc[0][X-1-1]-le,premax[1][X-1]-le,le};
									break;
								}
							}else{
								ans[0]={x,y,le};
								ans[1]={x-2,y-2,1};
								break;
							}
						}
					}
				}
				if(premin[0][X-1]>y||sufmax[1][Y+1]<x){
					if(x+le>=premax[1][Y]&&y-le<=sufmin[0][X]){ // bottom right stuff are within range
						if(premin[0][X-1]>y){
							if(Y<SZ(disc[1])){
								ll hor=sufmax[1][Y+1]-sufmin[1][Y+1];
								ll ver=premax[0][SZ(disc[0])]-disc[1][Y+1-1];
								if(max(hor,ver)<=le){
									ans[0]={x,y-le,le};
									ans[1]={sufmax[1][Y+1]-le,disc[1][Y+1-1],le};
									break;
								}
							}else{
								ans[0]={x,y-le,le};
								ans[1]={x-2,y-le-2,1};
								break;
							}
						}else{
							if(X>1){
								ll hor=disc[0][X-1-1]-premin[1][SZ(disc[1])];
								ll ver=premax[1][X-1]-premin[1][X-1];
								if(max(hor,ver)<=le){
									ans[0]={x,y-le,le};
									ans[1]={disc[0][X-1-1]-le,premin[1][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 (stderr)

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

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