Submission #793129

#	Time	Username	Problem	Language	Result	Execution time	Memory
793129		algorithm16	Gap (APIO16_gap)	C++14	0 / 100	3100 ms	1104 KiB

gap

#include "gap.h"
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
typedef long long int llint;
set <llint> s;
llint findGap(int T, int N)
{
	llint mn,mx;
	/*cout << 1 << " " << 1e18 << "\n";
	cin >> mn >> mx;*/
	MinMax(1LL,(llint)1e18,&mn,&mx);
	llint x=mn,y=mx,rr=mx-mn,r=(mx-mn)/(N-1)+((mx-mn)%(N-1)!=0);
	s.insert(mn);
	s.insert(mx);
	while(x!=y) {
		set <llint>::iterator it=s.lower_bound(x+r+1);
		it--;
		if((*it)!=x) {
			x=(*it);
			continue;
		}
		/*cout << x << " " << x+r << "\n";
		cin >> mn >> mx;*/
		MinMax(x+1,x+r,&mn,&mx);
		if(mx!=-1) {
			x=mx;
			continue;
		}
		llint lo=r,hi=min(y-x,r*3);
		while(lo<hi) {
			llint mid=(lo+hi)/2;
			/*cout << x << " " << x+mid << "\n";
			cin >> mn >> mx;*/
			MinMax(x+1,x+mid,&mn,&mx);
			s.insert(mn);
			s.insert(mx);
			if(mx!=-1) hi=mid;
			else lo=mid+1;
		}
		if(lo<r*3) x+=lo;
		r=lo;
	}
	return r;
}
/*int main()
{
	cout << findGap(1,5);
	return 0;
}*/

Compilation message (stderr)

gap.cpp: In function 'llint findGap(int, int)':
gap.cpp:14:18: warning: unused variable 'rr' [-Wunused-variable]
   14 |  llint x=mn,y=mx,rr=mx-mn,r=(mx-mn)/(N-1)+((mx-mn)%(N-1)!=0);
      |                  ^~

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