제출 #406370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
406370		inluminas	Gap (APIO16_gap)	C++14	0 / 100	65 ms	2636 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
 
using namespace std;
#define ll long long
#define endl "\n"
 
vector<ll>a;
ll len;
 
void f(ll L,ll R){
	if(R<L) return;
	ll mn,mx;
	MinMax(L,R,&mn,&mx);
	if(mn==-1) return;
	if(mn==mx){
		a.push_back(mn);
		return;
	}
	a.push_back(mn);
	a.push_back(mx);
	if(mn+1==mx) return;
	mn++,mx--;
	ll mid=(mn+mx)/2;
	if(mn<=mid && mid-mn+1>=len) f(mn,mid);
	if(mid<mx && mx-mid>=len ) f(mid+1,mx);
}
 
long long findGap(int T, int N)
{
 	
	ll mn,mx;
	MinMax(0,1e18,&mn,&mx);
	a.push_back(mn);
	a.push_back(mx);
	len=(mx-mn+2)/(N-1);
	mn++,mx--;
	ll mid=(mn+mx)/2;
	if(mn<=mid && mid-mn+1>=len) f(mn,mid);
	if(mid<mx && mx-mid>=len) f(mid+1,mx);


 
	sort(a.begin(),a.end());
	a.resize(unique(a.begin(),a.end())-a.begin());
	ll res=0;
	for(int i=1;i<N;i++){
		res=max(res,a[i]-a[i-1]);
	}
 
	return res;
}

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