제출 #1227590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227590		abdelhakim	Gap (APIO16_gap)	C++20	100 / 100	45 ms	3256 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ' ' << x<< endl;
#define ll long long 
using namespace std;
long long findGap(int T, int N)
{
	if(T==2)
	{vector<ll> a;
	ll l=0;
	ll r=0;
	MinMax(0,1e18,&l,&r);
	ll maxr=r;
	ll curl=l;
	ll sz=(((r-l-N+1)/(N-1)))+1;
	a.push_back(curl);
	while(curl<=maxr)
	{
		ll curr=min(maxr,curl+sz);
		MinMax(curl,curr,&l,&r);
		if(r!=-1)
		{a.push_back(l);
		a.push_back(r);}
		curl=curr+1;
	}
	a.push_back(maxr);
	ll ans=0;
	for (int i=1;i<a.size()-1;i++)
	{
		ans=max(ans,a[i]-a[i-1]);
	}
	return ans;}
	else
	{
			vector<ll> a(N);
	ll curl = 0;
	ll curr=1e18;
	ll l=0;
	ll r=N-1;
	while(l<=r)
	{
		ll mn=0; ll mx=0;
		MinMax(curl,curr,&mn,&mx);
		// cout << "here"<<endl;
		a[l]=(ll)mn;
		a[r]=(ll)mx;
		curl=(ll)mn+1;
		curr=(ll)mx-1;
		l++;r--;
	}
	ll mxd=0;
	for (int i=1;i<N;i++) 
	{
		mxd=max(mxd,a[i]-a[i-1]);
	}
	return mxd;
	}
}

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