Submission #106009

#	Time	Username	Problem	Language	Result	Execution time	Memory
106009		daniel920712	Gap (APIO16_gap)	C++14	12.89 / 100	83 ms	2040 KiB

gap

#include <iostream>
#include <algorithm>
#include "gap.h"

using namespace std;
int now=0;
long long all[100005];
void F(long long l,long long r)
{
    long long a,b;
    if(l>r) return;
    MinMax(l,r,&a,&b);
    if(a==-1) return ;
    //printf("%lld %lld %lld %lld\n",l,r,a,b);
    all[now++]=a;
    if(a!=b) all[now++]=b;
    if(b-1<=(l+r)/2||(l+r)/2+1<=a+1) F(a+1,b-1);
    else
    {
        F(a+1,(l+r)/2);
        F((l+r)/2+1,b-1);
    }

}
bool cmp(long long a,long long b)
{
    return  a<b;
}
long long findGap(int T,int N)
{
    long long a,b,l=0,r=N-1,x=0,y=1000000000000000000 ,ans=0;
    int i;
    F(x,y);
    sort(all,all+N,cmp);
    for(i=1;i<N;i++) ans=max(ans,all[i]-all[i-1]);
    return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:31:15: warning: unused variable 'a' [-Wunused-variable]
     long long a,b,l=0,r=N-1,x=0,y=1000000000000000000 ,ans=0;
               ^
gap.cpp:31:17: warning: unused variable 'b' [-Wunused-variable]
     long long a,b,l=0,r=N-1,x=0,y=1000000000000000000 ,ans=0;
                 ^
gap.cpp:31:19: warning: unused variable 'l' [-Wunused-variable]
     long long a,b,l=0,r=N-1,x=0,y=1000000000000000000 ,ans=0;
                   ^
gap.cpp:31:23: warning: unused variable 'r' [-Wunused-variable]
     long long a,b,l=0,r=N-1,x=0,y=1000000000000000000 ,ans=0;
                       ^

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