Submission #1073500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073500		Hugo1729	Gap (APIO16_gap)	C++11	100 / 100	32 ms	4340 KiB

gap

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


ll solve1(int N){
	ll s=0,t=1e18,ml=0,mr;

	vector<ll> ans,sus2;
	
	for(int i=0;i<N;i+=2){
		MinMax(s,t,&ml,&mr);

		if(mr==-1)break;

		ans.push_back(ml);
		if(ml==mr)break;
		sus2.push_back(mr);

		s=ml+1;
		t=mr-1;
	}

	for(int j=sus2.size()-1;j>=0;j--){
		ans.push_back(sus2[j]);
	}

	ll out=0;

	for(int i=0;i<N;i++){
		out=max(out,ans[i+1]-ans[i]);
	}

	// for(int i : ans)cout << i << ' ';
	// cout << '\n';
	

	return out;
}

ll solve2(int N){
	ll ml,mr;
	
	MinMax(0,1e18,&ml,&mr);

	ll lo=ml,hi=mr;
	ll L=hi-lo;
	ll sus=(L+N-2)/(N-1);

	ll ans = sus;

	ll prev=lo;

	for(ll i=ml+1;i<hi;i+=sus){
		sus=ans;
		MinMax(i,min(i+sus,hi-1),&ml,&mr);

		if(ml==-1)continue;

		ans=max(ans,ml-prev);

		prev=mr;
	}

	return max(ans,hi-prev);
}

ll findGap(int T, int N){
	if(T==1)return solve1(N);
	else return solve2(N);
}

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