Submission #51047

#	Time	Username	Problem	Language	Result	Execution time	Memory
51047		Abelyan	Gap (APIO16_gap)	C++17	100 / 100	84 ms	3592 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MX=(ll)1000000000000000000;
const int MAXN=100006;
ll a[MAXN];
vector<ll> v;

long long findGap(int T, int n)
{
	if (T==1){
		ll mx,mn;
		MinMax(0,MX,&mn,&mx);
		int j=n-1;
		int i=0;
		while (mn!=-1){
			a[i]=mn;
			a[j]=mx;
			//cout<<i<<" "<<" "<<j<<endl;
			//cout<<mn<< " "<<mx<<endl;
			i++;
			j--;
			if (i>j || mn+1>mx-1) break;
			MinMax(mn+1,mx-1,&mn,&mx);
			if (mn==mx && mn!=-1){
				a[i]=mn;
				break;
			}
	
		}
		ll maxim=0;
		for (int i=0;i<n-1;i++){
			//cout<<a[i]<<endl;
			maxim=max(maxim,a[i+1]-a[i]);
		}
		return maxim;
	}
	else{
		ll mx,mn;
		MinMax(0,MX,&mn,&mx);
		v.push_back(mn);
		ll del=(mx-mn-1)/(n-1);
		ll qan=mx-mn-1-(n-1)*del;
		//cout<<del<<" "<<qan<<endl;
		ll nax=mn;
		for (int i=0;i<n-1;i++){
			if (i<qan){
				ll l,r;
				MinMax(nax+1,nax+del+1,&l,&r);
				nax=nax+del+1;
				//cout<<l<<" "<<r<<endl;
				if (l!=-1){
					v.push_back(l);
					v.push_back(r);
				}
			}
			else{
				ll l,r;
				MinMax(nax+1,nax+del,&l,&r);
				nax=nax+del;
				if (l!=-1){
					v.push_back(l);
					v.push_back(r);
				}
			}
		}
		v.push_back(mx);
		ll maxim=0;
		for (int i=0;i<v.size()-1;i++){
			maxim=max(maxim,v[i+1]-v[i]);
		}
		return maxim;
	}
}

Compilation message (stderr)

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

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