제출 #398268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398268		tengiz05	Gap (APIO16_gap)	C++17	100 / 100	71 ms	1956 KiB

gap

#ifndef EVAL
#include "grader.cpp"
#endif
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll findGap(int T, int n){
	if(T == 1){
		ll ans = 0;
		ll l=0, r=1e18;
		vector<ll> a(n+1);
		ll mn, mx;
		int idl = 1, idr = n;
		while(idl <= idr){
			MinMax(l, r, &mn, &mx);
			a[idl] = mn;
			a[idr] = mx;
			l = mn+1, r = mx-1;
			idl++;
			idr--;
		}
		for(int i=2;i<=n;i++)ans = max(ans, a[i]-a[i-1]);
		return ans;
	}else {
		ll l=0, r=1e18;
		MinMax(l,r,&l,&r);
		if(r-l+1 == n){
			return 1;
		}
		ll len = (r-l+1)/n;
		if((r-l+1)%n)len++;
		ll ans = len;
		ll last = l;
		for(ll i=l;i<=r;i+=len){
			ll askl = i;
			if(askl == l)askl++;
			ll mn,mx;
			//~ cerr << "what the\n";
			MinMax(askl,min(i+len-1,r),&mn,&mx);
			//~ cerr << "OK\n";
			if(mn == -1)continue;
			ans = max(ans,mx-mn);
			ans = max(ans,mn - last);
			last = mx;
			//~ cout << ans << '\n';
		}
		return ans;
	}
}

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