Submission #108463

#	Time	Username	Problem	Language	Result	Execution time	Memory
108463		nxteru	Gap (APIO16_gap)	C++14	100 / 100	78 ms	3304 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
#define PB push_back
ll ans,mn,mx,n,l=-1,r=1e19+1;
vector<ll>x,y;
long long findGap(int t, int N)
{
	n=N;
	if(t==1){
		while(x.size()+y.size()<n){
			l++,r--;
			MinMax(l,r,&l,&r);
			x.PB(l);
			y.PB(r);
		}
	}else{
		MinMax(l,r,&l,&r);
		x.PB(l),y.PB(r);
		ll s=r-l+1LL;
		s/=n;
		s++;
		for(ll i=l;i+1<r;i+=s){
			ll nx=min(r-1,i+s);
			MinMax(i+1,nx,&mn,&mx);
			if(mn!=-1)x.PB(mn);
			if(mx!=-1)x.PB(mx);
		}
	}
	for(int i=y.size()-1;i>=0;i--)x.PB(y[i]);
	for(int i=0;i+1<x.size();i++)ans=max(ans,x[i+1]-x[i]);
	return ans;
}

Compilation message (stderr)

gap.cpp:6:27: warning: overflow in implicit constant conversion [-Woverflow]
 ll ans,mn,mx,n,l=-1,r=1e19+1;
                       ~~~~^~
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:12:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(x.size()+y.size()<n){
         ~~~~~~~~~~~~~~~~~^~
gap.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i+1<x.size();i++)ans=max(ans,x[i+1]-x[i]);
              ~~~^~~~~~~~~

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