Submission #105883

#	Time	Username	Problem	Language	Result	Execution time	Memory
105883		Pro_ktmr	Gap (APIO16_gap)	C++14	100 / 100	87 ms	2292 KiB

gap

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define MOD 1000000007

#include"gap.h"

//MinMax(LL s, LL t, LL& mn, LL& mx)
//aiのうちs以上の最小の数がmnに、aiのうちt以下の最大値がmxに格納される

//aiの差分のうち最大のものを返す
LL findGap(int T, int N){
	if(T == 1){
		LL m = 0LL;
		LL M = 1000000000000000000LL;
		vector<LL> v;
		for(int i=0; i<(N+1)/2; i++){
			LL tmp1, tmp2;
			MinMax(m, M, &tmp1, &tmp2);
			v.PB(tmp1);
			v.PB(tmp2);
			m = tmp1+1;
			M = tmp2-1;
		}
		sort(v.begin(), v.end());

		LL ans = 0;
		for(int i=1; i<v.size(); i++){
			ans = max(ans, v[i] - v[i-1]);
		}
		return ans;
	}
	if(T == 2){
		LL m, M;
		MinMax(0, 1000000000000000001LL, &m, &M);

		LL B = ceil((double)(M-m)/N);
		LL ans = B;

		LL l = m+1;
		LL r = l+B;
		LL last = m;
		for(int i=0; i<N; i++){
			if(r < l) break;
			LL tmp1, tmp2;
			MinMax(l, r-1, &tmp1, &tmp2);
			if(tmp1 != -1){
				ans = max(ans, tmp1-last);
				last = tmp2;
			}
			l = l+B;
			r = min(r+B,M);
		}
		ans = max(ans, M-last);

		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<v.size(); i++){
                ~^~~~~~~~~
gap.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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