oj.uz

Submission #421063

# Submission time Handle Problem Language Result Execution time Memory
421063 2021-06-08T17:04:22 Z Pyqe Izvanzemaljci (COI21_izvanzemaljci) C++14
56 / 100
 163 ms 14788 KB 
#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,c=0;
	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=ma*3;
			y=ma*3-c*2;
			w=1;
			c++;
		}
		printf("%lld %lld %lld\n",x,y,w);
	}
}

Compilation message

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,c=0;
      |                                            ^~~
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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 107 ms 14772 KB Output is correct
8 Correct 107 ms 14788 KB Output is correct
9 Correct 106 ms 14784 KB Output is correct
10 Correct 112 ms 14788 KB Output is correct
11 Correct 110 ms 14736 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 131 ms 14624 KB Output is correct
11 Correct 110 ms 14524 KB Output is correct
12 Correct 109 ms 14488 KB Output is correct
13 Correct 123 ms 14532 KB Output is correct
14 Correct 109 ms 14520 KB Output is correct
15 Correct 113 ms 14532 KB Output is correct
16 Correct 108 ms 14512 KB Output is correct
17 Correct 97 ms 13460 KB Output is correct
18 Correct 92 ms 13164 KB Output is correct
19 Correct 95 ms 11888 KB Output is correct
20 Correct 90 ms 12740 KB Output is correct
21 Correct 107 ms 14584 KB Output is correct
22 Correct 108 ms 14552 KB Output is correct
23 Correct 110 ms 14608 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 440 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 440 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 440 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 444 KB Output is correct
7 Correct 2 ms 560 KB Output is correct
8 Correct 2 ms 440 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 440 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Incorrect 163 ms 12800 KB Output isn't correct
15 Halted 0 ms 0 KB -