Submission #160839

#	Time	Username	Problem	Language	Result	Execution time	Memory
160839		nafis_shifat	Gap (APIO16_gap)	C++14	100 / 100	115 ms	1912 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;

const ll inf=1e18;
ll solve1(int N)
{
	int n=N;
	ll a[n];
	int id=0;

	ll l1=0;
	ll l2=inf;
	ll mn,mx;
	while(n>0)
	{
	    
		MinMax(l1,l2,&mn,&mx);
		if(mx!=mn)n-=2;
		else n--;
		a[id]=mn;
		a[N-id-1]=mx;
		id++;
		l1=mn+1;
		l2=mx-1;
	
	}
	ll c=0;

	for(int i=1;i<N;i++)c=max(c,a[i]-a[i-1]);
	return c;
}
ll solve2(int N)
{
	ll mx,mn;
	mx=mn=-1;

	MinMax(0,inf,&mn,&mx);


	ll sm=mn;
	ll up=mx;
	ll off=(mx-mn-1)/N;

	ll lst=sm;
	ll cur=0;

	ll pnt=sm+1;
	
	for(int i=1;i<N;i++)
	{

		MinMax(pnt,pnt+off-1,&mn,&mx);
		if(mn!=-1)
		{
			cur=max(cur,mn-lst);
			lst=mx;
		}
		pnt+=off;
	}

	MinMax(pnt,up-1,&mn,&mx);

	if(mn!=-1)
	{
		cur=max(cur,mn-lst);
		cur=max(cur,up-mx);
	}
	else
	{
		cur=max(cur,up-lst);
	}


	return cur;





}
long long findGap(int T, int N)
{
	if(T==1)return solve1(N);
	return solve2(N);

}

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