Submission #99935

#	Time	Username	Problem	Language	Result	Execution time	Memory
99935		TadijaSebez	Gap (APIO16_gap)	C++11	43.01 / 100	109 ms	2540 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll lim=1e18;
ll findGap(int T, int N)
{
	if(T==1)
	{
		ll a,b,c=-1,d=-1;
		ll l=0,r=lim,ans=0;
		vector<ll> v;
		while(l<=r && v.size()<N)
		{
			MinMax(l,r,&a,&b);
			if(a!=-1) v.push_back(a);
			if(b!=a) v.push_back(b);
			l=a+1;r=b-1;
		}
		sort(v.begin(),v.end());
		for(int i=1;i<v.size();i++) ans=max(ans,v[i]-v[i-1]);
		return ans;
	}
	else
	{
		vector<ll> v;
        function<void(ll,ll)> Solve=[&](ll l, ll r)
        {
        	if(l>r || v.size()==N) return;
        	ll a,b;
        	MinMax(l,r,&a,&b);
        	if(a==-1) return;
        	v.push_back(a);
        	if(a!=b) v.push_back(b);
        	else return;
        	ll mid=a+b>>1;
        	Solve(a+1,mid);
        	Solve(mid+1,b-1);
        };
		Solve(1,lim);
		ll ans=0;
		sort(v.begin(),v.end());
		for(int i=1;i<v.size();i++) ans=max(ans,v[i]-v[i-1]);
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:13:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(l<=r && v.size()<N)
                 ~~~~~~~~^~
gap.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<v.size();i++) ans=max(ans,v[i]-v[i-1]);
               ~^~~~~~~~~
gap.cpp:10:10: warning: unused variable 'c' [-Wunused-variable]
   ll a,b,c=-1,d=-1;
          ^
gap.cpp:10:15: warning: unused variable 'd' [-Wunused-variable]
   ll a,b,c=-1,d=-1;
               ^
gap.cpp: In lambda function:
gap.cpp:29:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          if(l>r || v.size()==N) return;
                    ~~~~~~~~^~~
gap.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
          ll mid=a+b>>1;
                 ~^~
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<v.size();i++) ans=max(ans,v[i]-v[i-1]);
               ~^~~~~~~~~

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