Submission #107342

#	Time	Username	Problem	Language	Result	Execution time	Memory
107342		maruii	Gap (APIO16_gap)	C++14	100 / 100	77 ms	3352 KiB

gap

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

long long findGap(int T, int N){
	long long mn, mx, s=0, e=1e18, ans = 0;
	if(T==1){
		int i=0, j=N-1;
		vector<long long> vec(N);
		while(i<=j){
			MinMax(s, e, &mn, &mx);
			vec[i++] = mn, vec[j--] = mx;
			s = mn+1, e = mx-1;
		}
		for(int i=1; i<N; ++i) ans = max(ans, abs(vec[i]-vec[i-1]));
		return ans;
	}
	MinMax(0, 1e18, &mn, &mx);
	s = mn, e = mx;
	if(N==2) return e-s;
	long long d = (e-s-1)/(N-1)+1;
	vector<pair<long long, long long> > vec;
	vec.emplace_back(s, s);
	for(int i=1; i<N; ++i){
		MinMax(s+1+(i-1)*d, s+1+i*d-1, &mn, &mx);
		if(mn != -1) vec.emplace_back(mn, mx);
	}
	for(int i=1; i<vec.size(); ++i) ans = max(ans, vec[i].first - vec[i-1].second);
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vec.size(); ++i) ans = max(ans, vec[i].first - vec[i-1].second);
               ~^~~~~~~~~~~

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