Submission #313441

#	Time	Username	Problem	Language	Result	Execution time	Memory
313441		nandonathaniel	Gap (APIO16_gap)	C++14	100 / 100	75 ms	2840 KiB

gap

#include "gap.h"
#include "bits/stdc++.h"
using namespace std;
long long findGap(int T, int N)
{
	if(T==1){
		vector<long long> kiri,kanan;
		long long ki=0,ka=1e18,mn,mx;
		for(int i=1;i<=(N+1)/2;i++){
			MinMax(ki,ka,&mn,&mx);
			kiri.push_back(mn);
			if(mn!=mx)kanan.push_back(mx);
			ki=mn+1;ka=mx-1;
		}
		reverse(kanan.begin(),kanan.end());
		for(auto isi : kanan)kiri.push_back(isi);
		long long ans=0;
		for(int i=1;i<kiri.size();i++)ans=max(ans,kiri[i]-kiri[i-1]);
		return ans;
	}
	long long mn,mx;
	MinMax(0,1e18,&mn,&mx);
	//mn+1...mx-1 bagi N-1 segment
	//PHP ada 1 segment yang kosong
	//Gap maximumnya beda segment
	long long bagi=(mx-mn-1)/(N-1);
	int sisa=(mx-mn-1)%(N-1);
	long long ki=mn+1,last=mn,ujungka=mx,ans=0;
	for(int i=1;i<N;i++){
		if(i<=sisa){
			MinMax(ki,ki+bagi,&mn,&mx);
			ki+=(bagi+1);
		}
		else{
			MinMax(ki,ki+bagi-1,&mn,&mx);
			ki+=bagi;
		}
		if(mn!=-1){
			ans=max(ans,mn-last);
			last=mx;
		}
	}
	ans=max(ans,ujungka-last);
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i=1;i<kiri.size();i++)ans=max(ans,kiri[i]-kiri[i-1]);
      |               ~^~~~~~~~~~~~

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