Submission #336866

#	Time	Username	Problem	Language	Result	Execution time	Memory
336866		seedkin	Gap (APIO16_gap)	C11	30 / 100	66 ms	2064 KiB

gap

#include "gap.h"
#include <stdio.h>

long long arr[100001];

long long findGap(int T, int N)
{
	if(T == 1) {
		long long min = 0;
		long long max = 1e18;
		int minIdx = 0;
		int maxIdx = N-1;

		int maxIter = (N+1)/2;
		long long low;
		long long high;
		for(int i = 0; i < maxIter; i++) {
			MinMax(min, max, &low, &high);
			arr[minIdx++] = low;
			arr[maxIdx--] = high;
			min = low+1;
			max = high-1;
		}
		long long result = 0;
		for(int i =0; i < N-1; i++) {
			if(arr[i+1] - arr[i] > result ) result = arr[i+1] - arr[i];
		}
		// for(int i =0 ; i< N ; i++) {
		// 	printf("%lld ", arr[i]);
		// }
		// printf("\n");
		return result;
	} else {
		long long min = 0;
		long long max = 1e18;
		
		long long low;
		long long high;
		MinMax(min, max, &low, &high);
		min = low;
		max = high;

		long long distance = (high - low + N - 2) / (N - 1);
		long long result = 0;
		int cmp = low;
		long long left = min+1;
		long long right = left + distance;

		while(1) {
			if(left >= max) break;
			if(right >= max) right = max - 1;	
			MinMax(left, right, &low, &high);
			// printf("left %d, right %d, low %lld, high %lld\n", left, right, low, high);
			left = right + 1;
			right = left + distance;			
			if(low == -1) continue;
			if(result < low - cmp) result = low - cmp;
			cmp = high;
		}
		if(max - cmp > result) result = max - cmp;
		return result;
	}

	return 0;
}

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