Submission #300094

#	Time	Username	Problem	Language	Result	Execution time	Memory
300094		a_player	Gap (APIO16_gap)	C++14	0 / 100	76 ms	2040 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
long long findGap(int T, int N){
  if(T==1){
    ll mx, mn;
    vector<ll> a(N);
    MinMax(0,2e18,&mn,&mx);
    a[0]=mn;
    a[N-1]=mx;
    for(int i=1;i<(N+1)/2;i++){
      ll mnn,mxx;
      MinMax(mn+1,mx-1,&mnn,&mxx);
      if(mnn==-1)break;
      a[i]=mnn;
      a[N-i-1]=mxx;
      mn=mnn;
      mx=mxx;
    }
    ll ans=0;
    for(int i=1;i<N;i++)ans=max(ans,a[i]-a[i-1]);
    cout<<ans;
    return 0;
  }
  ll mn,mx;
  MinMax(0,2e18,&mn,&mx);
  ll d=(mx-mn+N-1)/N;
  ll a=mn+1;
  ll b=mn+d;
  ll l=mn;
  ll ans=0;
  for(int i=0;i<N;i++){
    if(b>=mx)b=mx-1;
    if(a>b)break;
    ll mnn,mxx;
    MinMax(a,b,&mnn,&mxx);
    if(mnn!=-1){
      ans=max(ans,mnn-l);
      l=mxx;
    }
    a+=d;
    b+=d;
  }
  ans=max(ans,mx-l);
  cout<<ans;
  return 0;
}

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