Submission #59930

#	Time	Username	Problem	Language	Result	Execution time	Memory
59930		babo	Sparklers (JOI17_sparklers)	C++14	0 / 100	4 ms	664 KiB

sparklers

#include <bits/stdc++.h>
#define L long long

using namespace std;

L N,K,T;
L loc[100010];
L a[100010];

L vlfdy[100010];
L gain[100010];


bool ok(L x,L det){
	L t=x*T*2;
	L i,s=K,e=K,health;
	/*while(s>1&&e<N)
	{
		printf("%lld %lld %lld\n",s,e,left);
		L t1=loc[s]-loc[s-1];
		L t2=loc[e+1]-loc[e];
		if(t1<t2)
		{
			if(t1>left) return 0;
			left=left-t1+t;
			s--;
		}
		else
		{
			if(t2>left) return 0;
			left=left-t2+t;
			e++;
		}
	}
	while(s>1)
	{
		printf("%lld %lld %lld\n",s,e,left);
		L t1=loc[s]-loc[s-1];
		if(t1>left) return 0;
		left=left-t1+t;
		s--;
	}
	while(e<N)
	{
		printf("%lld %lld %lld\n",s,e,left);
		L t2=loc[e+1]-loc[e];
		if(t2>left) return 0;
		left=left-t2+t;
		e++;
	}*/
	for(i=1;i<=N;i++)
	{
		vlfdy[i]=gain[i]=0;
	}
	queue<L>lloc,lvlfdy,lgain;
	queue<L>rloc,rvlfdy,rgain;
	//printf("***%lld %lld***\n",x,t);
	
	health=0;
	for(i=K-1;i>=1;i--)
	{
		health+=loc[i+1]-loc[i];
		vlfdy[i]=max(vlfdy[i+1],health);
		health-=t;
		gain[i]=-health;
		if(gain[i]>0)
		{
			//printf("%lld %lld %lld\n",i,vlfdy[i],gain[i]);
			lloc.push(i);
			lvlfdy.push(vlfdy[i]);
			lgain.push(gain[i]);
			health=0;
			vlfdy[i]=0;
		}
	}
	health=0;
	for(i=K+1;i<=N;i++)
	{
		health+=loc[i]-loc[i-1];
		vlfdy[i]=max(vlfdy[i-1],health);
		health-=t;
		gain[i]=-health;		
		if(gain[i]>0)
		{
			//printf("%lld %lld %lld\n",i,vlfdy[i],gain[i]);
			rloc.push(i);
			rvlfdy.push(vlfdy[i]);
			rgain.push(gain[i]);
			health=0;
			vlfdy[i]=0;
		}
	}
	/*for(i=1;i<=N;i++)
	{
		printf("%lld %lld\n",vlfdy[i],gain[i]);
	}*/
	health=t;
	while(!lloc.empty()&&!rloc.empty())
	{
		if(lvlfdy.front()<=health)
		{
			health+=lgain.front();
			s=lloc.front();
			lloc.pop();
			lvlfdy.pop();
			lgain.pop();
		}
		else if(rvlfdy.front()<=health)
		{
			health+=rgain.front();
			e=rloc.front();
			rloc.pop();
			rvlfdy.pop();
			rgain.pop();
		}
		else return 0;
	}
	while(!lloc.empty())
	{
		if(lvlfdy.front()<=health)
		{
			health+=lgain.front();
			s=lloc.front();
			lloc.pop();
			lvlfdy.pop();
			lgain.pop();
		}
		else return 0;
	}
	while(!rloc.empty())
	{
		if(rvlfdy.front()<=health)
		{
			health+=rgain.front();
			e=rloc.front();
			rloc.pop();
			rvlfdy.pop();
			rgain.pop();
		}
		else return 0;
	}
	
	//printf("%lld %lld\n",s,e);
	if(det==1)
	{
		while(e<N)
		{
			//printf("%lld %lld %lld\n",s,e,left);
			L t2=loc[e+1]-loc[e];
			if(t2>health) return 0;
			health=health-t2+t;
			e++;
		}
		while(s>1)
		{
			//printf("%lld %lld %lld\n",s,e,left);
			L t1=loc[s]-loc[s-1];
			if(t1>health) return 0;
			health=health-t1+t;
			s--;
		}
	}
	else
	{
		while(s>1)
		{
			//printf("%lld %lld %lld\n",s,e,left);
			L t1=loc[s]-loc[s-1];
			if(t1>health) return 0;
			health=health-t1+t;
			s--;
		}
		while(e<N)
		{
			//printf("%lld %lld %lld\n",s,e,left);
			L t2=loc[e+1]-loc[e];
			if(t2>health) return 0;
			health=health-t2+t;
			e++;
		}
	}
	return 1;
}

L bin(L s,L e){
	if(s==e) return s;
	L mid=(s+e)/2;
	if(ok(mid,1)||ok(mid,2)) return bin(s,mid);
	else return bin(mid+1,e);
}

int main()
{
	scanf("%lld %lld %lld",&N,&K,&T);
	L i,st;
	for(i=1;i<=N;i++)
	{
		scanf("%lld",&loc[i]);
	}
	st=loc[K];
	for(i=1;i<=N;i++)
	{
		loc[i]-=st;
	}
	L temp=bin(0,1000000001);
	if(temp==1000000001) while(1)
	{
		L asdf=10/0;
	}
	printf("%lld",temp);
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:208:12: warning: division by zero [-Wdiv-by-zero]
   L asdf=10/0;
          ~~^~
sparklers.cpp:208:5: warning: unused variable 'asdf' [-Wunused-variable]
   L asdf=10/0;
     ^~~~
sparklers.cpp:194:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&N,&K,&T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&loc[i]);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50