Submission #712723

#	Time	Username	Problem	Language	Result	Execution time	Memory
712723		dungnguyenn_05	Gap (APIO16_gap)	C++17	59.04 / 100	58 ms	1188 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
#define fs first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;

ll dis,L,R=1e18;

pi pos(int u)
{
	ll val=(L+(dis*u)-1);
	if(R-val<=dis) 
		val=R;

	return {L+dis*(u-1),val};
}

long long findGap(int T, int N)
{
	ll s=0,t=1e18,mn,mx;
	MinMax(s,t,&L,&R);

	if(N==2)
		return R-L;

	dis=(R-L+1)/(N-1);

	ll st=-1,cnt=0,res=0;

	while(st==-1)
	{
		cnt++;
		pi val=pos(cnt);
		MinMax(val.fs,val.sc,&mn,&st);
	}

	for(int i=cnt+1;;i++)
	{
		pi val=pos(i);
		MinMax(val.fs,val.sc,&mn,&mx);
		if(mn==-1) continue;

		res=max(res,mn-st);

		st=mx;

		if(mx==R) break;
	}

	return res;
}

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