제출 #978198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978198		Amaarsaa	Gap (APIO16_gap)	C++14	30 / 100	44 ms	2268 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll =long long;
ll Sub1(ll N) {
	ll b[N + 2],ans, lo1, hi1, lo, hi, l, r;
	l = 1;
	r = N;
	lo = 0;
	hi = LONG_MAX;
	while ( l <= r) {
		MinMax(lo, hi, &lo1, &hi1);
		if (lo1 == -1) break;
		b[l] = lo1;
		b[r] = hi1;
		lo = lo1 + 1;
		hi = hi1 - 1;
		l ++;
		r --;
	}
	ans = 0;
	for (int i = 2; i <= N; i ++) {
		ans =max(ans, b[i] - b[i - 1]);
	}
	return ans;
}
ll Sub2(ll N) {
	
	ll l, r, x, y, ans, n = N, s, i;
	MinMax(0, 1e18, &l, &r);
	s = (r - l +1 + n - 2)/(n - 1);
	ans = s;
	for ( i = l; i + s< r; i += (s + 1)) {
		MinMax(i, i + s, &x, &y);
		if ( x != -1) {
			ans =max(ans, x - l);
			l = y;
		}
	}
	MinMax(i, r, &x, &y);
	if ( x != -1) ans = max(ans, x- l);
	return ans;
}
long long findGap(int T, int N) {
	if ( T == 1) {
		return Sub1(N); 
	}
	else return Sub2(N);
}

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