oj.uz

Submission #420865

# Submission time Handle Problem Language Result Execution time Memory
420865 2021-06-08T14:30:00 Z Pyqe Izvanzemaljci (COI21_izvanzemaljci) C++14
26 / 100
 117 ms 12836 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;
pair<long long,long long> a[4][100069],as[4][100069];
pair<pair<long long,long long>,long long> ca[3],sq[3];

int main()
{
	long long i,j,ii,im,x,y,k,l,w,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
			{
				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

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

Subtask #1
5.0 / 5.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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 107 ms 12812 KB Output is correct
8 Correct 108 ms 12700 KB Output is correct
9 Correct 108 ms 12732 KB Output is correct
10 Correct 107 ms 12736 KB Output is correct
11 Correct 105 ms 12800 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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 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 Correct 1 ms 332 KB Output is correct
10 Correct 110 ms 12720 KB Output is correct
11 Correct 111 ms 12740 KB Output is correct
12 Correct 109 ms 12792 KB Output is correct
13 Correct 112 ms 12808 KB Output is correct
14 Correct 117 ms 12836 KB Output is correct
15 Correct 110 ms 12724 KB Output is correct
16 Correct 110 ms 12720 KB Output is correct
17 Correct 96 ms 11716 KB Output is correct
18 Correct 92 ms 11304 KB Output is correct
19 Correct 86 ms 10280 KB Output is correct
20 Correct 90 ms 10980 KB Output is correct
21 Correct 107 ms 12736 KB Output is correct
22 Correct 108 ms 12740 KB Output is correct
23 Correct 108 ms 12808 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Integer 0 violates the range [1, 2*10^9]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Integer 0 violates the range [1, 2*10^9]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Integer 0 violates the range [1, 2*10^9]
2 Halted 0 ms 0 KB -