Submission #199986

#	Time	Username	Problem	Language	Result	Execution time	Memory
199986		mohammedehab2002	Gap (APIO16_gap)	C++11	64.63 / 100	66 ms	1912 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long solve(int n)
{
	long long f,l,ans=0;
	MinMax(0,1e18,&f,&l);
	deque<long long> d1({f}),d2({l});
	while (d1.size()+d2.size()<n)
	{
		MinMax(f+1,l-1,&f,&l);
		d1.push_back(f);
		d2.push_front(l);
	}
	for (int i=1;i<d1.size();i++)
	ans=max(ans,d1[i]-d1[i-1]);
	for (int i=1;i<d2.size();i++)
	ans=max(ans,d2[i]-d2[i-1]);
	return max(ans,d2.front()-d1.back());
}
long long findGap(int t,int n)
{
	if (t==1 || n<=10)
	return solve(n);
	long long f,l;
	MinMax(0,1e18,&f,&l);
	long long p=f+1,g=1;
	while (p<=l)
	{
		long long mn,mx;
		MinMax(p,p+g-1,&mn,&mx);
		if (mn==-1)
		{
			while (mn==-1)
			{
				g*=2;
				MinMax(p,p+g,&mn,&mx);
			}
			g=mn-p+1;
		}
		p=mx+1;
	}
	return g;
}

Compilation message (stderr)

gap.cpp: In function 'long long int solve(int)':
gap.cpp:9:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (d1.size()+d2.size()<n)
         ~~~~~~~~~~~~~~~~~~~^~
gap.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<d1.size();i++)
               ~^~~~~~~~~~
gap.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<d2.size();i++)
               ~^~~~~~~~~~

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