Submission #170998

#	Time	Username	Problem	Language	Result	Execution time	Memory
170998		taulant	Gap (APIO16_gap)	C++14	100 / 100	75 ms	2040 KiB

gap

#include "gap.h"
typedef long long ll;

ll findGap(int T, int n){
	if(T == 1){
		ll arr[100100];
		ll i=0, j=n-1;
		ll minval=0, maxval=1000000000000000000;
		while(i<j){
			MinMax(minval, maxval, &minval, &maxval);
			arr[i++]=minval++;
			arr[j--]=maxval--;
		}
		if(i == j){
			MinMax(minval, maxval, &minval, &maxval);
			arr[i]=minval;
		}
		ll diff=0;
		for(int j=1; j<n; ++j){
			if(arr[j]-arr[j-1] > diff) diff = arr[j]-arr[j-1];
		}
		return diff;
	}
	else {
		ll first=0, last=1000000000000000000;
		MinMax(first, last, &first, &last);
		ll l = last - first - 1;
		ll mod = l % n;
		ll diff = l/n;
		ll start = first + 1;
		ll a, b;
		ll latest = first;
		for(int i=0; i<mod; ++i){
			MinMax(start, start + l/n + (mod != 0) - 1, &a, &b);
			if(a >= 0){
				if(a - latest >= diff) diff = a - latest;
				latest = b;
			}
			start = start + l/n + (mod != 0);

		}
		for(int i=mod; i<n; ++i){
			MinMax(start, start + l/n - 1, &a, &b);
			if(a >= 0){
				if(a - latest >= diff) diff = a - latest;
				latest = b;
			}
			start+=l/n;
		}
		if(last - latest >= diff) diff = last - latest;
		return diff;
	}
}

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