제출 #1367590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367590		sporknives	Gap (APIO16_gap)	C++20	89.02 / 100	28 ms	1932 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long findGap(int T, int N)
{
	int n = N;
	if(T==1) {
		ll l=0,r=n-1,s=0,e=1e18;
		vector<ll> a(n);
		ll r1=0,r2=0;
		while(l<=r) {
			MinMax(s,e,&r1,&r2);
			a[l]=r1,a[r]=r2;
			l++; r--;
			s=r1+1;
			e=r2-1;
		}
		ll res=0;
		for(int i=0;i<n-1;i++) {
			res=max(res,a[i+1]-a[i]);
		}
		return res;
	}
	else {
		ll l,r;
		MinMax(0,1e18,&l,&r);
		if(n==2) return r-l;
		ll block_size = (r-l+1) / (n-1);
		ll prev=l;
		ll ans=0;
		for(ll i=l;i<=r;i+=block_size) {
			ll mn=0,mx=0;
			MinMax(i,i+block_size-1,&mn,&mx);
			if(mn==-1) continue;
			ans=max(ans,mn-prev);
			prev=mx;
		}
		ans=max(ans,r-prev);
		return ans;
	}
}

• 서브태스크 1: 30 / 30
• 서브태스크 2: 59.0204 / 70