Submission #68484

#	Time	Username	Problem	Language	Result	Execution time	Memory
68484		KLPP	Gap (APIO16_gap)	C++14	100 / 100	113 ms	3552 KiB

gap

#include "gap.h"
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long lld;
long long maximo(lld a, lld b){
if(a<b)return b;
return a;
}
long long minimo(lld a, lld b){
if(a<b)return a;
return b;
}
long long findGap(int T, int N)
{
	if(T==1){
		vector<lld> numeros;
		lld a,b;
		a=0;
		b=1000000000000000000;
		while(a!=-1 && numeros.size()<N){//cout<<a<<" "<<b<<endl;
			lld A,B;
			MinMax(a,b,&A,&B);
			a=A;
			b=B;
			if(a!=-1){
				numeros.push_back(a);
				numeros.push_back(b);
				a++;b--;
			}
		}
		sort(numeros.begin(),numeros.end());
		lld max=0;
		for(int i=0;i<numeros.size()-1;i++){
			max=maximo(max,numeros[i+1]-numeros[i]);
		}
		return max;
	}
	lld min,max;
	MinMax(0,1000000000000000000,&min,&max);
	lld Maxlength=(max-min-1)/N;
	Maxlength++;
	vector<lld> candidates;
	candidates.push_back(min);
	for(lld i=min+1;i<max;i+=Maxlength){
		lld s=i;
		lld t=minimo(i+Maxlength-1,max);
		lld c1,c2;
		MinMax(s,t,&c1,&c2);
		if(c1!=-1){
			candidates.push_back(c1);
			candidates.push_back(c2);
		}
	}candidates.push_back(max);
	for(int i=0;i<candidates.size()-1;i++){
		Maxlength=maximo(Maxlength,candidates[i+1]-candidates[i]);
	}
	return Maxlength;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:22:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(a!=-1 && numeros.size()<N){//cout<<a<<" "<<b<<endl;
                  ~~~~~~~~~~~~~~^~
gap.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<numeros.size()-1;i++){
               ~^~~~~~~~~~~~~~~~~
gap.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<candidates.size()-1;i++){
              ~^~~~~~~~~~~~~~~~~~~~

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