Submission #105738

#	Time	Username	Problem	Language	Result	Execution time	Memory
105738		Pro_ktmr	Gap (APIO16_gap)	C++14	0 / 100	99 ms	2808 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){
	queue<pair<LL,LL>> kukan;
	kukan.push(MP(0LL, 1000000000000000000LL));
	vector<LL> v;
	while(kukan.size() > 0){
		LL m = kukan.front().first;
		LL M = kukan.front().second;
		kukan.pop();
		LL tmp1, tmp2;
		MinMax(m, M, &tmp1, &tmp2);
		if(tmp1 == -1) continue;
		v.PB(tmp1);
		if(tmp1 == tmp2) continue;
		v.PB(tmp2);
		
		LL mid = (tmp1+tmp2) / 2;
		kukan.push(MP(tmp1+1, mid));
		kukan.push(MP(mid+1, 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;
}

Compilation message (stderr)

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

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