Submission #112245

#	Time	Username	Problem	Language	Result	Execution time	Memory
112245		user202729	Gap (APIO16_gap)	C++17	70 / 100	61 ms	1272 KiB

gap

#include "gap.h"
#include<vector>
// #include<iostream>

using ll=long long;
ll findGap(int t, int n)
{
	if(t==2){
		ll a0,an;
		MinMax(0,1000000000000000000LL,&a0,&an);
		int n_gap=n-1;
		ll const sum_gap=an-a0;
		ll const min_gap=(sum_gap+n_gap-1)/n_gap;

		// std::cerr<<"a0 an min_gap="<<a0<<' '<<an<<' '<<min_gap<<'\n';

		// divide [a0..an] into [a0..a0+min_gap[, [a0+min_gap..a0+2*min_gap[, ...
		// the last segment should contain an

		ll _,prev_end; // max value of last segment
		MinMax(a0+1,a0+min_gap-1,&_,&prev_end);
		if(prev_end==-1)prev_end=a0;

		ll start_next=a0+min_gap;
		ll ans=min_gap;

		while(an>=start_next){
			ll cur_start,cur_end;
			MinMax(start_next,start_next+min_gap-1,&cur_start,&cur_end);

			if(cur_end!=-1){
				ans=std::max(ans,cur_start-prev_end);

				// std::cerr<<"sg "<<start_next<<' '<<start_next+min_gap-1<<' '
				// 	<<"ans="<<cur_start<<'-'<<prev_end<<"="<<cur_start-prev_end<<"\n";

				prev_end=cur_end;
			} // otherwise this segment is empty

			start_next+=min_gap;
		}

		return ans;
	}
	return 0;
}

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