Submission #108943

#	Time	Username	Problem	Language	Result	Execution time	Memory
108943		autumn_eel	Gap (APIO16_gap)	C++14	100 / 100	91 ms	3308 KiB

gap

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

#include "gap.h"


ll solve1(int n){
	deque<ll>f,r;
	while(f.size()+r.size()<n){
		ll mn,mx;
		ll L=0,R=1e18;
		if(!f.empty())L=f.back()+1;
		if(!r.empty())R=r.front()-1;
		MinMax(L,R,&mn,&mx);
		f.push_back(mn);
		if(mn!=mx)r.push_front(mx);
	}
	while(!r.empty()){
		f.push_back(r.front());
		r.pop_front();
	}
	ll ans=0;
	rep(i,n-1)ans=max(ans,f[i+1]-f[i]);
	return ans;
}

ll solve2(int n){
	ll mn,mx;
	MinMax(0,1e18,&mn,&mx);
	ll x=((mx-mn)+n-1)/(n-1);
	vector<ll>v;
	ll cur=mn;
	while(cur<=mx){
		ll a,b;
		MinMax(cur,cur+x,&a,&b);
		if(a!=-1){
			v.push_back(a);
			v.push_back(b);
		}
		cur+=x+1;
	}
	ll ans=0;
	rep(i,v.size()-1){
		ans=max(ans,v[i+1]-v[i]);
	}
	return ans;
}

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

Compilation message (stderr)

gap.cpp: In function 'll solve1(int)':
gap.cpp:11:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(f.size()+r.size()<n){
        ~~~~~~~~~~~~~~~~~^~
gap.cpp: In function 'll solve2(int)':
gap.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
gap.cpp:45:2: note: in expansion of macro 'rep'
  rep(i,v.size()-1){
  ^~~

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