oj.uz

Submission #744377

# Submission time Handle Problem Language Result Execution time Memory
744377 2023-05-18T13:58:14 Z jamielim Izvanzemaljci (COI21_izvanzemaljci) C++14
26 / 100
 56 ms 6368 KB 
#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;
int premin[100005];
int premax[100005];
int sufmin[100005];
int sufmax[100005];

vector<ii> one_input;
inline vector<ll> find_one_square(){
	if(SZ(one_input)==0)return {0,0,1};
	ll minx=LLINF,maxx=-LLINF,miny=LLINF,maxy=-LLINF;
	for(ii i:one_input){
		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};
}
vector<ll> an[2];
vector<ii> two_input;
inline vector<vector<ll> > find_two_squares(){
	one_input=two_input;
	an[0]=find_one_square();
	an[1]={2012345678,2012345678,1};
	ll le=an[0][2];
	sort(ALL(two_input));
	for(int i=0;i<n;i++){
		if(i==0){
			premin[i]=two_input[i].se;
			premax[i]=two_input[i].se;
		}else{
			premin[i]=min(premin[i-1],two_input[i].se);
			premax[i]=max(premax[i-1],two_input[i].se);
		}
	}
	for(int i=n-1;i>=0;i--){
		if(i==n-1){
			sufmin[i]=two_input[i].se;
			sufmax[i]=two_input[i].se;
		}else{
			sufmin[i]=min(sufmin[i+1],two_input[i].se);
			sufmax[i]=max(sufmax[i+1],two_input[i].se);
		}
	}
	for(int i=0;i<n-1;i++){
		ll l1=max(max(two_input[i].fi-two_input[0].fi,premax[i]-premin[i]),1);
		ll l2=max(max(sufmax[i+1]-sufmin[i+1],two_input[n-1].fi-two_input[i+1].fi),1);
		ll l=max(l1,l2);
		if(l<le){
			le=l;
			an[0]={two_input[i].fi-l1,premin[i],l1};
			an[1]={two_input[i+1].fi,sufmin[i+1],l2};
		}
		/*
		ll hor=max(max(two_input[i].fi-two_input[0].fi,two_input[n-1].fi-two_input[i+1].fi),1);
		ll ver=max(max(premax[i]-premin[i],sufmax[i+1]-sufmin[i+1]),1);
		ll l=max(hor,ver);
		if(l<le){
			le=l;
			an[0]={two_input[i].fi-l,premax[i]-l,l};
			an[1]={two_input[i+1].fi,sufmin[i+1],l};
		}*/
	}
	
	for(int i=0;i<n;i++)swap(two_input[i].fi,two_input[i].se);
	sort(ALL(two_input));
	for(int i=0;i<n;i++){
		if(i==0){
			premin[i]=two_input[i].se;
			premax[i]=two_input[i].se;
		}else{
			premin[i]=min(premin[i-1],two_input[i].se);
			premax[i]=max(premax[i-1],two_input[i].se);
		}
	}
	for(int i=n-1;i>=0;i--){
		if(i==n-1){
			sufmin[i]=two_input[i].se;
			sufmax[i]=two_input[i].se;
		}else{
			sufmin[i]=min(sufmin[i+1],two_input[i].se);
			sufmax[i]=max(sufmax[i+1],two_input[i].se);
		}
	}
	for(int i=0;i<n-1;i++){
		ll l1=max(max(two_input[i].fi-two_input[0].fi,premax[i]-premin[i]),1);
		ll l2=max(max(sufmax[i+1]-sufmin[i+1],two_input[n-1].fi-two_input[i+1].fi),1);
		ll l=max(l1,l2);
		if(l<le){
			le=l;
			an[0]={premin[i],two_input[i].fi-l1,l1};
			an[1]={sufmin[i+1],two_input[i+1].fi,l2};
		}
		/*
		ll hor=max(max(two_input[i].fi-two_input[0].fi,two_input[n-1].fi-two_input[i+1].fi),1);
		ll ver=max(max(premax[i]-premin[i],sufmax[i+1]-sufmin[i+1]),1);
		ll l=max(hor,ver);
		if(l<le){
			le=l;
			an[0]={premax[i]-l,two_input[i].fi-l,l};
			an[1]={sufmin[i+1],two_input[i+1].fi,l};
		}*/
	}
	for(int i=0;i<n;i++)swap(two_input[i].fi,two_input[i].se);
	return {an[0],an[1]};
}
/*
inline vector<vector<ll> > find_two_part(){
	// top right and bottom right
	one_input=two_input;
	an[0]=find_one_square();
	an[1]={2012345678,2012345678,1};
	ll le=an[0][2];
	for(int i=0;i<n;i++)swap(two_input[i].fi,two_input[i].se);
	sort(ALL(two_input));
	for(int i=0;i<n;i++){
		if(i==0){
			premin[i]=two_input[i].se;
			premax[i]=two_input[i].se;
		}else{
			premin[i]=min(premin[i-1],two_input[i].se);
			premax[i]=max(premax[i-1],two_input[i].se);
		}
	}
	for(int i=n-1;i>=0;i--){
		if(i==n-1){
			sufmin[i]=two_input[i].se;
			sufmax[i]=two_input[i].se;
		}else{
			sufmin[i]=min(sufmin[i+1],two_input[i].se);
			sufmax[i]=max(sufmax[i+1],two_input[i].se);
		}
	}
	for(int i=0;i<n-1;i++){
		ll l1=max(max(two_input[i].fi-two_input[0].fi,premax[i]-premin[i]),1);
		ll l2=max(max(sufmax[i+1]-sufmin[i+1],two_input[n-1].fi-two_input[i+1].fi),1);
		ll l=max(l1,l2);
		if(l<le){
			le=l;
			an[0]={premin[i],two_input[i].fi-l1,l1};
			an[1]={sufmin[i+1],two_input[i+1].fi,l2};
		}
	}

	for(int i=0;i<n;i++)swap(two_input[i].fi,two_input[i].se);
	return {an[0],an[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);
	}
	if(k==1){
		one_input=all;
		vector<ll> ans=find_one_square();
		printf("%lld %lld %lld\n",ans[0],ans[1],ans[2]);
	}else if(k==2){
		two_input=all;
		vector<vector<ll> > ans=find_two_squares();
		for(int i=0;i<2;i++){for(int j=0;j<3;j++)printf("%lld ",ans[i][j]);printf("\n");}
	}else{
		two_input=all;
		vector<vector<ll> > ans=find_two_squares();
		vector<ll> tmp={2012345688,2012345688,1};
		ans.pb(tmp);
		if(n<=2){
			for(int i=0;i<3;i++){for(int j=0;j<3;j++)printf("%lld ",ans[i][j]);printf("\n");}
			return 0;
		}
		vector<vector<ll> > a;
		vector<ii> v;
		
		//printf("1\n");
		sort(ALL(all));
		vector<int> disc;
		for(int i=0;i<n;i++){
			if(i==0)disc.pb(i);
			else if(all[i].fi>all[i-1].fi)disc.pb(i);
		}
		int pmin[n],pmax[n];
		for(int i=0;i<n;i++){
			if(i==0){pmin[i]=all[i].se;pmax[i]=all[i].se;}
			else{pmin[i]=min(pmin[i-1],all[i].se);pmax[i]=max(pmax[i-1],all[i].se);}
		}
		int l=1,r=SZ(disc)-1;
		while(l<r){
			//printf("%d %d\n",l,r);
			int m=(l+r+1)/2;
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			int L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			if(L>max(a[0][2],a[1][2]))r=m-1;
			else l=m;
		}
		for(int m=l;m<=l+1;m++){
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			ll L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			ll maxl=max(L,max(a[0][2],a[1][2]));
			if(maxl<max(max(ans[0][2],ans[1][2]),ans[2][2])){
				ans[0]=a[0];
				ans[1]=a[1];
				ans[2]={all[idx-1].fi-L,pmin[idx-1],L};
			}
		}
		
		//printf("2\n");
		for(int i=0;i<n;i++)all[i].fi=-all[i].fi;
		sort(ALL(all));
		disc.clear();
		for(int i=0;i<n;i++){
			if(i==0)disc.pb(i);
			else if(all[i].fi>all[i-1].fi)disc.pb(i);
		}
		for(int i=0;i<n;i++){
			if(i==0){pmin[i]=all[i].se;pmax[i]=all[i].se;}
			else{pmin[i]=min(pmin[i-1],all[i].se);pmax[i]=max(pmax[i-1],all[i].se);}
		}
		l=1;r=SZ(disc)-1;
		while(l<r){
			int m=(l+r+1)/2;
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			int L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			if(L>max(a[0][2],a[1][2]))r=m-1;
			else l=m;
		}
		for(int m=l;m<=l+1;m++){
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			ll L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			ll maxl=max(L,max(a[0][2],a[1][2]));
			if(maxl<max(max(ans[0][2],ans[1][2]),ans[2][2])){
				a[0][0]=-a[0][0];a[1][0]=-a[1][0];
				ans[0]=a[0];
				ans[1]=a[1];
				ans[2]={-all[idx-1].fi,pmin[idx-1],L};
			}
		}
		
		//printf("3\n");
		for(int i=0;i<n;i++){all[i].fi=-all[i].fi;swap(all[i].fi,all[i].se);}
		sort(ALL(all));
		disc.clear();
		for(int i=0;i<n;i++){
			if(i==0)disc.pb(i);
			else if(all[i].fi>all[i-1].fi)disc.pb(i);
		}
		for(int i=0;i<n;i++){
			if(i==0){pmin[i]=all[i].se;pmax[i]=all[i].se;}
			else{pmin[i]=min(pmin[i-1],all[i].se);pmax[i]=max(pmax[i-1],all[i].se);}
		}
		l=1,r=SZ(disc)-1;
		while(l<r){
			int m=(l+r+1)/2;
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			int L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			if(L>max(a[0][2],a[1][2]))r=m-1;
			else l=m;
		}
		for(int m=l;m<=l+1;m++){
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			ll L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			ll maxl=max(L,max(a[0][2],a[1][2]));
			if(maxl<max(max(ans[0][2],ans[1][2]),ans[2][2])){
				swap(a[0][0],a[0][1]);swap(a[1][0],a[1][1]);
				ans[0]=a[0];
				ans[1]=a[1];
				ans[2]={pmin[idx-1],all[idx-1].fi-L,L};
			}
		}
		
		//printf("4\n");
		for(int i=0;i<n;i++)all[i].fi=-all[i].fi;
		sort(ALL(all));
		disc.clear();
		for(int i=0;i<n;i++){
			if(i==0)disc.pb(i);
			else if(all[i].fi>all[i-1].fi)disc.pb(i);
		}
		for(int i=0;i<n;i++){
			if(i==0){pmin[i]=all[i].se;pmax[i]=all[i].se;}
			else{pmin[i]=min(pmin[i-1],all[i].se);pmax[i]=max(pmax[i-1],all[i].se);}
		}
		l=1;r=SZ(disc)-1;
		while(l<r){
			int m=(l+r+1)/2;
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			int L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			if(L>max(a[0][2],a[1][2]))r=m-1;
			else l=m;
		}
		for(int m=l;m<=l+1;m++){
			int idx=disc[m];
			v.clear();
			for(int i=idx;i<n;i++)v.pb(all[i]);
			two_input=v;
			a=find_two_squares();
			ll L=max(max(all[idx-1].fi-all[0].fi,pmax[idx-1]-pmin[idx-1]),1);
			ll maxl=max(L,max(a[0][2],a[1][2]));
			if(maxl<max(max(ans[0][2],ans[1][2]),ans[2][2])){
				a[0][0]=-a[0][0];a[1][0]=-a[1][0];
				swap(a[0][0],a[0][1]);swap(a[1][0],a[1][1]);
				ans[0]=a[0];
				ans[1]=a[1];
				ans[2]={pmin[idx-1],-all[idx-1].fi,L};
			}
		}
		
		for(int i=0;i<3;i++){for(int j=0;j<3;j++)printf("%lld ",ans[i][j]);printf("\n");}
	}
}
/*
5 2
1 3
3 1
5 5
5 10
7 7

5 3
1 3
3 1
5 5
5 10
7 7
*/

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 26 ms 3940 KB Output is correct
8 Correct 24 ms 3924 KB Output is correct
9 Correct 30 ms 4012 KB Output is correct
10 Correct 27 ms 3904 KB Output is correct
11 Correct 29 ms 3908 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 56 ms 6368 KB Output is correct
11 Correct 43 ms 6340 KB Output is correct
12 Correct 45 ms 6284 KB Output is correct
13 Correct 43 ms 6332 KB Output is correct
14 Correct 46 ms 6336 KB Output is correct
15 Correct 42 ms 6312 KB Output is correct
16 Correct 40 ms 6264 KB Output is correct
17 Correct 41 ms 5768 KB Output is correct
18 Correct 39 ms 5560 KB Output is correct
19 Correct 42 ms 5060 KB Output is correct
20 Correct 39 ms 5448 KB Output is correct
21 Correct 42 ms 6336 KB Output is correct
22 Correct 46 ms 6284 KB Output is correct
23 Correct 48 ms 6208 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 32.0

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