Submission #156668

#	Time	Username	Problem	Language	Result	Execution time	Memory
156668		a_player	Gap (APIO16_gap)	C++14	44.36 / 100	131 ms	2040 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;
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==1){
     ric(u,u);
      ric(v,v);
      return;
    }
    if(v-u==2){
     ric(u,u);
      ric(u+1,u+1);
      ric(v,v);
      return;
    }
	ll m=(v-u)/3;
	ric(u,u+m);
    ric(u+m+1,u+2*m);
	ric(u+2*m+1,v);
	}
int findGap(int T,int N){
    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: 14.3575041502 / 70