Submission #476353

#	Time	Username	Problem	Language	Result	Execution time	Memory
476353		ponytail	Gap (APIO16_gap)	C++17	100 / 100	56 ms	1948 KiB

gap

#include "gap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
 
long long findGap(int T, int N){
    long long arr[N];
    if(T==1){
        long long idx=0,mx,mn,l=0,r=1e18;
        for(int i=0;i<N/2+(N%2);i++){
            MinMax(l,r,&mn,&mx);
            arr[i]=mn;
            arr[N-i-1]=mx;
            l=mn+1;
            r=mx-1;
        }
    }
    else{
        long long idx=0,mx,mn,l=0,r=1e18;
        MinMax(l,r,&mn,&mx);
        l=mn;
        r=mx;
        long long extra=(r-l+N-2)/(N-1);
        for(long long i=l+1;i<r;){
            MinMax(i,i+extra-1,&mn,&mx);
            if(mx!=-1){
                i=mx+1;
                continue;
            }
            for(long long  j=2;;j++){
                MinMax(i,i+j*extra-1,&mn,&mx);
                if(mn!=-1){
                    extra=mn-i+1,i=mx+1;
                    break;
                }
            }
        }
        return extra;
    }
    long long ans=0;
    for(int i=0;i<N-1;i++)
        ans=max(ans,arr[i+1]-arr[i]);
    return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:9:19: warning: unused variable 'idx' [-Wunused-variable]
    9 |         long long idx=0,mx,mn,l=0,r=1e18;
      |                   ^~~
gap.cpp:19:19: warning: unused variable 'idx' [-Wunused-variable]
   19 |         long long idx=0,mx,mn,l=0,r=1e18;
      |                   ^~~

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