Submission #1015297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015297		vjudge1	Gap (APIO16_gap)	C++17	0 / 100	42 ms	1240 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

bool adj(ll x,ll y)
{
	long long a, b;
	MinMax(x+1,y-1,&a,&b);
	return a==-1;
}

long long findGap(signed t,signed n)
{
	if (t==2 && n>60)
	{
		ll mn1,mx1;
		MinMax(0,(ll)1e18,&mn1,&mx1);
		ll st,mn,mx,ans=0;
		for (int i=0;i<=60;i++)
		{
			MinMax(mn1+1,mn1+(1LL<<i),&mn,&mx);
			if (mn!=-1)
			{
				ans=mn-mn1;
				st=mx;
				break;
			}
		}
		while (st<mx1)
		{
			MinMax(st+1,st+ans,&mn,&mx);
			if (mn!=-1)
				st=mx;
			else
			{
				ll val=ans*2;
				while (1)
				{
					MinMax(st+1,st+val,&mn,&mx);
					if (mn!=-1)
					{
						ans=mn-st;
						st=mx;
						break;
					}
					val*=2;
				}
			}
		}
		return ans;
	}
	else
	{
		long long lim1=0,lim2=1e18;
		long long mn,mx,mn1,mx1;
		MinMax(lim1,lim2,&mn1,&mx1);
		if (n==2)
			return mx1-mn1;
		MinMax(mn1+1,mx1-1,&mn,&mx);
		ll ans = max(mn-mn1,mx1-mx);
		while (mn+ans*2<=mx)
		{
			MinMax(mn+ans,mx-ans,&mn1,&mx1);
			if (mn1==-1)
				break;
			if (adj(mn,mn1))
				ans=mn1-mn;
			if (adj(mx1,mx))
				ans=max(ans,mx-mx1);
			mn=mn1,mx=mx1;
		}
		if (mn+ans<mx)
		{
			MinMax(mn+ans+1,mx,&mn1,&mx1);
			if (mn1!=-1)
				ans=mn1-mn;
			else
			{
				MinMax(mn,mx-ans-1,&mn1,&mx1);
				if (mx1!=-1)
					ans=mx-mx1;
			}
		}
		
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:45:10: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |       ans=mn-st;
      |       ~~~^~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70