Submission #420920

#	Time	Username	Problem	Language	Result	Execution time	Memory
420920		Pyqe	Izvanzemaljci (COI21_izvanzemaljci)	C++14	56 / 100	173 ms	14840 KiB

izvanzemaljci

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long ma=1e9,inf=1e18;
long long n,d,nn;
pair<long long,long long> a[4][100069],as[4][100069],a2[100069];
pair<pair<long long,long long>,long long> ca[3],sq[3];
bitset<100069> vtd;

int main()
{
	long long i,j,ii,im,x,y,k,l,w,p,mn,mx,mn2,mx2,lh,rh,md;
	bool bad;
	
	scanf("%lld%lld",&n,&d);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		a[0][i]={x,y};
	}
	for(im=0;im<4;im++)
	{
		sort(a[im]+1,a[im]+n+1);
		for(i=1;i<=n;i++)
		{
			as[im][i]={a[im][i].sc,i};
		}
		sort(as[im]+1,as[im]+n+1);
		if(im<3)
		{
			for(i=1;i<=n;i++)
			{
				x=a[im][i].fr;
				y=a[im][i].sc;
				a[im+1][i]={y,-x};
			}
		}
	}
	for(lh=1,rh=ma*2;lh<=rh;)
	{
		md=(lh+rh)/2;
		bad=0;
		for(im=0;im<4;im++)
		{
			if(d==1)
			{
				if(!im)
				{
					mn=inf;
					mx=-inf;
					mn2=inf;
					mx2=-inf;
					for(i=1;i<=n;i++)
					{
						x=a[im][i].fr;
						y=a[im][i].sc;
						mn=min(mn,y);
						mx=max(mx,y);
						if(mx-mn>md||x-a[im][1].fr>md)
						{
							break;
						}
						mn2=mn;
						mx2=mx;
					}
					if(i>n)
					{
						bad=1;
						sq[0]={{a[im][1].fr,mn2},md};
					}
				}
			}
			else if(d==2)
			{
				if(im<2)
				{
					l=0;
					for(ii=0;ii<2;ii++)
					{
						mn=inf;
						mx=-inf;
						k=l;
						mn2=inf;
						mx2=-inf;
						for(i=l+1;i<=n;i++)
						{
							x=a[im][i].fr;
							y=a[im][i].sc;
							mn=min(mn,y);
							mx=max(mx,y);
							if(mx-mn>md||x-a[im][l+1].fr>md)
							{
								break;
							}
							if(i==n||x!=a[im][i+1].fr)
							{
								k=i;
								mn2=mn;
								mx2=mx;
							}
						}
						if(!ii)
						{
							ca[ii]={{a[im][k].fr-md,mn2},md};
						}
						else
						{
							ca[ii]={{a[im][l+1].fr,mn2},md};
						}
						l=k;
					}
					if(i>n)
					{
						bad=1;
						for(j=0;j<d;j++)
						{
							sq[j]=ca[j];
						}
					}
				}
			}
			else
			{
				mn=inf;
				mx=-inf;
				k=0;
				mn2=inf;
				mx2=-inf;
				vtd.reset();
				for(i=1;i<=n;i++)
				{
					p=as[im][i].sc;
					x=a[im][p].fr;
					y=a[im][p].sc;
					mn=min(mn,x);
					mx=max(mx,x);
					if(mx-mn>md||y-as[im][1].fr>md)
					{
						break;
					}
					if(i==n||y!=as[im][i+1].fr)
					{
						mn2=mn;
						mx2=mx;
						for(;k<i;)
						{
							k++;
							vtd[as[im][k].sc]=1;
						}
					}
				}
				ca[0]={{mn2,as[im][k].fr-md},md};
				nn=0;
				for(i=1;i<=n;i++)
				{
					if(!vtd[i])
					{
						nn++;
						a2[nn]=a[im][i];
					}
				}
				l=0;
				for(ii=0;ii<2;ii++)
				{
					mn=inf;
					mx=-inf;
					k=l;
					mn2=inf;
					mx2=-inf;
					for(i=l+1;i<=nn;i++)
					{
						x=a2[i].fr;
						y=a2[i].sc;
						mn=min(mn,y);
						mx=max(mx,y);
						if(mx-mn>md||x-a2[l+1].fr>md)
						{
							break;
						}
						if(i==nn||x!=a2[i+1].fr)
						{
							k=i;
							mn2=mn;
							mx2=mx;
						}
					}
					if(!ii)
					{
						ca[ii+1]={{a2[k].fr-md,mn2},md};
					}
					else
					{
						ca[ii+1]={{a2[l+1].fr,mn2},md};
					}
					l=k;
				}
				if(i>nn)
				{
					bad=1;
					for(j=0;j<d;j++)
					{
						sq[j]=ca[j];
					}
				}
				if(im<2)
				{
					
				}
			}
			for(i=0;i<d;i++)
			{
				x=sq[i].fr.fr;
				y=sq[i].fr.sc;
				w=sq[i].sc;
				sq[i].fr={y,-x-w};
			}
		}
		if(bad)
		{
			rh=md-1;
		}
		else
		{
			lh=md+1;
		}
	}
	for(i=0;i<d;i++)
	{
		x=sq[i].fr.fr;
		y=sq[i].fr.sc;
		w=sq[i].sc;
		if(x<-ma*3||y<-ma*3||x>ma*3||y>ma*3)
		{
			x=min(max(x,-ma*3),ma*3);
			y=min(max(y,-ma*3),ma*3);
			w=1;
		}
		printf("%lld %lld %lld\n",x,y,w);
	}
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:17:44: warning: variable 'mx2' set but not used [-Wunused-but-set-variable]
   17 |  long long i,j,ii,im,x,y,k,l,w,p,mn,mx,mn2,mx2,lh,rh,md;
      |                                            ^~~
izvanzemaljci.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%lld%lld",&n,&d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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