Submission #162970

#	Time	Username	Problem	Language	Result	Execution time	Memory
162970		HungAnhGoldIBO2020	Gap (APIO16_gap)	C++14	100 / 100	80 ms	4552 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
const long long inf=1e18;
long long findGap(int T,int N){
	if(T==2){
		long long min1,max1;
		MinMax(0,inf,&min1,&max1);
		long long num=max1-min1-1;
		assert(num>=N-2);
		long long val=num/(N-1),cnt=num%(N-1);
		long long ans=val,now=min1+1,now1,dum,dum1;
		vector<long long> ans_lis;
		ans_lis.push_back(min1);
		for(int i=1;i<N;i++){
			now1=now+val-1;
			if(cnt){
				cnt--;
				now1++;
			}
			if(now<=now1){
				MinMax(now,now1,&dum,&dum1);
				now=now1+1;
				if(dum!=-1){
					ans_lis.push_back(dum);
					ans_lis.push_back(dum1);
				}
			}
		}
		ans_lis.push_back(max1);
		for(int i=0;i<ans_lis.size()-1;i++){
			ans=max(ans,ans_lis[i+1]-ans_lis[i]);
		}
		return ans;
	}
	else{
		long long min1=-1,max1=inf+1,ans=0;
		vector<long long> ans_lis,ans_lis1;
		for(int i=1;i<=(N+1)/2;i++){
			assert(min1+1<=max1-1);
			MinMax(min1+1,max1-1,&min1,&max1);
			assert(min1!=-1&&max1!=-1);
			ans_lis.push_back(min1);
			ans_lis1.push_back(max1);
		}
		while(ans_lis1.size()){
			ans_lis.push_back(ans_lis1.back());
			ans_lis1.pop_back();
		}
		for(int i=0;i+1<ans_lis.size();i++){
			ans=max(ans,ans_lis[i+1]-ans_lis[i]);
		}
		return ans;
	}
}

Compilation message (stderr)

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

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