Submission #156682

#	Time	Username	Problem	Language	Result	Execution time	Memory
156682		a_player	Gap (APIO16_gap)	C++14	37.08 / 100	1650 ms	2124 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
ll mas=0;
ll vv[100001];
int k=0;
int N;
ll pivot=8LL;
void ric(ll a,ll b){
	ll u,v;
	MinMax(a,b,&u,&v);
	if(u==-1&&v==-1)return;
	if(u==v){vv[k++]=u;
		return;}
    if(v-u<pivot){
      for(ll i=u;i<=v;i++)ric(i,i);
      return;
    }
    ll m=(v-u)/pivot;
    ric(u,u+m);
    for(ll i=1LL;i<=(ll)(pivot-2);i++)ric(u+i*m+1LL,u+(i+1LL)*m);
     ric(u+(ll)(pivot-1)*m+1,v);
	}
int findGap(int T,int N){
  ::N=N;
  pivot=(ll)sqrt(N)+1LL;
    if(T==2){
      ll g=1;
      for(int i=0;i<18;i++)g*=10LL;
	ric(0LL,g);
	for(int i=0;i<N;i++)mas=max(mas,vv[i+1]-vv[i]);
      return mas;
    }
    	ll a=0,b=1000000000000000000;
  int i=0,j=N-1;
  while(i<=j){
    MinMax(a,b,&a,&b);
    vv[i]=a;
    vv[j]=b;
    i++;
    j--;
    a++;
    b--;
  }
  for(int i=0;i<N-1;i++)mas=max(mas,vv[i+1]-vv[i]);
  
	return mas;
}

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