oj.uz

Submission #744153

# Submission time Handle Problem Language Result Execution time Memory
744153 2023-05-18T08:43:34 Z zaneyu Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
 323 ms 7564 KB 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
pii arr[maxn];
int n,k;
bool splx;
pii pmn,pmx;
bool wk(int mid){
	vector<int> va,vb,bth;
	REP(i,n){
		if(arr[i].f-arr[0].f>mid and arr[n-1].f-arr[i].f>mid){
			return false;
		}
		if(arr[i].f-arr[0].f<=mid and arr[n-1].f-arr[i].f<=mid){
			bth.pb(arr[i].s);
		}
		else if(arr[i].f-arr[0].f<=mid){
			va.pb(arr[i].s);
		}
		else{
			vb.pb(arr[i].s);
		}
	}
	sort(ALL(va)),sort(ALL(vb)),sort(ALL(bth));
	REP(a,2){
		int mn=INF,mx=-INF;
		if(sz(va)) mn=va[0],mx=va.back();
		int p=-1;
		int pv=mn;
		REP(i,sz(bth)){
			MNTO(mn,bth[i]),MXTO(mx,bth[i]);
			if(mx-mn>mid) break;
			pv=mn;
			p=i;
		}
		int asd=pv;
		mn=INF,mx=-INF;
		if(sz(vb)) mn=vb[0],mx=vb.back();
		for(int i=p+1;i<sz(bth);i++){
			MNTO(mn,bth[i]),MXTO(mx,bth[i]);
		}
		if(mx-mn<=mid){
			pmn={arr[0].f,asd},pmx={max(arr[0].f+mid+1,arr[n-1].f-mid),mn};
			if(a==1){
				swap(pmn.f,pmx.f);
			}
			return true;
		}
		swap(va,vb);
	}
	return false;
}	
bool inter(int a,int b,int c,int d){
	return max(a,c)>=min(b,d);
}
int main(){
	
	cin>>n>>k;
	REP(i,n){
		cin>>arr[i].f>>arr[i].s;
	}
	vector<int> vx,vy;
	REP(i,n) vx.pb(arr[i].f),vy.pb(arr[i].s);
	sort(ALL(vx)),sort(ALL(vy));
	if(k==1){
		cout<<vx[0]<<' '<<vy[0]<<' '<<max({1,vx.back()-vx[0],vy.back()-vy[0]});
		return 0;
	}
	sort(arr,arr+n);
	if(n==1){
		cout<<arr[0].f-1<<' '<<arr[0].s-1<<" 1\n";
		cout<<arr[0].f+1<<' '<<arr[0].s+1<<" 1\n";
		return 0;
	}
	int bst=INT_MAX;

	pii a,b;
	REP(asd,2){
		multiset<ll> ma,mb;
		REP(i,n){
			ma.insert(arr[i].s);
		}
		REP(i,n-1){
			ma.erase(ma.find(arr[i].s));
			mb.insert(arr[i].s);
			int cur=max({1LL,((*ma.rbegin())-(*ma.begin())),((*mb.rbegin())-(*mb.begin())),arr[i].f-arr[0].f,arr[n-1].f-arr[i+1].f});
			if(cur<bst){
				int pp=(*mb.rbegin())-cur,p2=(*ma.begin());
				if(arr[i+1].f==arr[i].f and inter(pp,pp+cur,p2,p2+cur)) continue;
				bst=cur;
				a={arr[i].f-cur,pp};
				b={arr[i+1].f,p2};
				if(asd==1) swap(a.f,a.s),swap(b.f,b.s);
			}
		}
		REP(i,n) swap(arr[i].f,arr[i].s);
		sort(arr,arr+n);
	}
	assert(bst!=INT_MAX);
	cout<<a.f<<' '<<a.s<<' '<<bst<<'\n';
	cout<<b.f<<' '<<b.s<<' '<<bst<<'\n';
	REP(i,n) assert(max(arr[i].f-a.f,arr[i].s-a.s)<=bst or max(arr[i].f-b.f,arr[i].s-b.s)<=bst);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 91 ms 2852 KB Output is correct
8 Correct 94 ms 2760 KB Output is correct
9 Correct 89 ms 2968 KB Output is correct
10 Correct 89 ms 2864 KB Output is correct
11 Correct 98 ms 2860 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 258 ms 7564 KB Output is correct
11 Correct 298 ms 7460 KB Output is correct
12 Correct 323 ms 7452 KB Output is correct
13 Correct 278 ms 7496 KB Output is correct
14 Correct 301 ms 7364 KB Output is correct
15 Correct 270 ms 7476 KB Output is correct
16 Correct 251 ms 7476 KB Output is correct
17 Correct 264 ms 6836 KB Output is correct
18 Correct 231 ms 6540 KB Output is correct
19 Correct 217 ms 6024 KB Output is correct
20 Correct 218 ms 6500 KB Output is correct
21 Correct 309 ms 7356 KB Output is correct
22 Correct 280 ms 7476 KB Output is correct
23 Correct 275 ms 7400 KB Output is correct

Subtask #3
0 / 12.0

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