제출 #336855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336855		seedkin	Gap (APIO16_gap)	C11	30 / 100	56 ms	2032 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;
		int minIdx = 0;
		int maxIdx = N-1;
		
		long long low;
		long long high;
		MinMax(min, max, &low, &high);
		min = low;
		max = high;

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

		while(1) {
			if(left >= max) break;			
			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(right >= max) right = max - 1;
			if(low == -1) continue;
			if(result < low - cmp) result = low - cmp;
			cmp = high;
		}
		if(max - cmp > result) result = max - cmp;
		return result;
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

gap.c: In function 'findGap':
gap.c:37:7: warning: unused variable 'maxIdx' [-Wunused-variable]
   37 |   int maxIdx = N-1;
      |       ^~~~~~
gap.c:36:7: warning: unused variable 'minIdx' [-Wunused-variable]
   36 |   int minIdx = 0;
      |       ^~~~~~

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