Submission #712720

#	Time	Username	Problem	Language	Result	Execution time	Memory
712720		dungnguyenn_05	Gap (APIO16_gap)	C++17	59.02 / 100	61 ms	1164 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)
{
	return {L+dis*(u-1),min(R,L+(dis*u)-1)};
}

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.0203916407 / 70