Submission #238192

#	Time	Username	Problem	Language	Result	Execution time	Memory
238192		thtsshz_bgwrswh	Gap (APIO16_gap)	C++17	30 / 100	76 ms	2336 KiB

gap

#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<vector>
#include<assert.h>
#include<algorithm>
#include "gap.h"
using namespace std;
vector<long long> num;
long long findGap(int T,int N){
	long long i;
	if(T==1){
		long long i,maxv=1000000000000000000,minv=0,ans,ans2;
		while(maxv>=minv&&num.size()<N){
			MinMax(minv,maxv,&ans,&ans2);
			if(ans==-1||ans2==-1)
				break;
			if(ans==ans2){
				num.emplace_back(ans);
				break;
			}
			num.emplace_back(ans);
			num.emplace_back(ans2);
			maxv=ans2-1;
			minv=ans+1;
		}
		sort(num.begin(),num.end());
		ans=0;
		for(i=1;i<num.size();i++)
			ans=max(ans,num[i]-num[i-1]);
		return ans;
	}
	else{
		long long minv,maxv;
		MinMax(0,1000000000000000000,&minv,&maxv);
		long long block=(maxv-minv)/(N-1);
		long long ans=block,pre=minv,l,r;
		for(i=minv+1;i+block-1<maxv;i+=block){
			MinMax(i,i+block-1,&l,&r);
			if(pre!=-1&&l!=-1)
				ans=max(ans,l-pre);
			if(r!=-1)
				pre=r;
		}
		if(i<=maxv&&pre!=-1){
			MinMax(i,maxv-1,&l,&r);
			if(l!=-1)
				ans=max(ans,l-pre);
			if(r!=-1)
				ans=max(ans,maxv-r);
		}	
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:13:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(maxv>=minv&&num.size()<N){
                     ~~~~~~~~~~^~
gap.cpp:28:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=1;i<num.size();i++)
           ~^~~~~~~~~~~

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